Atcoder Grand Contest 009 E. Eternal Average

Atcoder Grand Contest 009 E. Eternal Average

E: Eternal Average - AtCoder Grand Contest 009 | AtCoder

感想

実装軽いのに考察が重すぎる...。

解法

最終的に残る数を$\ x\ $とする。$\ x\ $は連分数で書かれるような数になるが、このまま考えるとわかりにくいので、これを完全$\ K\ $分木で考える。各葉には$\ 1, 0\ $が書かれていて、その親ノードにはその平均が書かれている。

この根ノードに書かれた数が$\ x\ $になるが、これはそれぞれの葉の深さを$\ depth_i\ $とし、書かれた数を$\ p_i = \{ 0, 1 \}\ $とすると、$\ x = \sum K^{-depth_i} * p_i\ $となる。

さて、$\ 0\ $と書かれたノードの深さの列を$\ a_1, a_2, ..., a_n\ $、$\ 1\ $と書かれたノードの深さの列を$\ b_1, b_2, ..., b_m\ $とする。このとき次の条件を得る。

$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} + K^{-b_1} + K^{-b_2} + ... + K^{b_m} = 1\ $

これは気づきにくいが、木を書いてみればわかる。逆にこの条件が成り立つとき、その$\ x\ $が残るように木が構成できることも言える。さらに上に書いた$\ x\ $を用いて書きなおすと、

$\ K^{-b_1} + K^{-b_2} + ... + K^{-b_m} = x\ $
$\ K^{-a_1} + K^{-a_2} + ... + K^{-a_n} = 1 - x\ $

となる。

次に、$\ K\ $進法によって$\ x = 0.d_1d_2...d_l\ $、$\ 1 - x = 0.e_1e_2...e_l\ $と書く。ただし$\ d_l \neq 0, e_l \neq 0\ $とする。これについて満たすべき条件というのは、以下のようになる。

$\ \sum d_i \equiv m\ (mod\ K - 1)\ ...(A)\ $
$\ \sum e_i \equiv n\ (mod\ K - 1)\ ...(B)\ $

なぜかというと、$\ b_i\ $の各項が増えるごとに、ある桁に$\ 1\ $が足されるはずなので、$\ b_i\ $の項数が$\ m\ $であるならば$\ m\ $回$\ 1\ $が加えられているはずだが、繰り上がりを考慮すると、$\ K - 1 + 1 \equiv 1\ $であるため、$\ mod\ K - 1\ $で考えると$\ \sum d_i \equiv m\ $となっているはずだからである。同様に2番目の式も出てくる。

さらにこれらの和は$\ 1\ $になることから、次が言える。

$\ d_i + e_i = K - 1\ (i = l)\ $
$\ d_i + e_i = K\ (i \neq l)\ $

これを用いると、上の$\ (B)\ $を変形することができて、

$\ \sum_{i = 1}^{l - 1} (K - d_i - 1) + (K - d_l) \equiv n\ (mod\ K - 1)\ $

$\ lK - \sum_{i = 1}^{l} d_i - (l - 1) \equiv n\ (mod\ K - 1)\ $

よって以下を得る。

$\ l = \cfrac{n + \sum_{i = 1}^{l} d_i - 1}{k - 1}\ ...(C)\ $

さて、次の$\ dp\ $を考える。

$\ dp[i][j] := \ $ ($\ i\ $番目までの$\ d\ $を定めて$\ x\ $を構成したときに、その各桁の総和が$\ j\ $であるような場合の数）

この$\ dp\ $を計算し、上の条件$\ (A), (C)\ $を満たすようなものについての総和をとれば答えになる。

実装

#include <cstdio>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

signed main() {
        int n, m, k;
        scanf(&quot;%d%d%d&quot;, &n, &m, &k);
        int c = (n + m - 1) / (k - 1);
        vector<vector<long long>> dp(c + 1, vector<long long> (m + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= c; i ++) {
                for (int j = 0; j <= m; j ++) {
                        for (int l = 0; l < k && j + l <= m; l ++) {
                                (dp[i][j + l] += dp[i - 1][j]) %= MOD;
                        }
                }
        }
        long long ans = 0;
        while (m > 0) {
                int nc = (n + m - 1) / (k - 1);
                (ans += dp[nc][m]) %= MOD;
                m -= k - 1;
        }
        printf(&quot;%lld\n&quot;, ans);
        return 0;
}