SRM 埋めを始めたいと思う! ところでこの問題、こんなの気付かないよ...!! まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。
問題概要
10 進法表記で最高次数から順に広義単調増加であるような整数を Increasing Number と呼ぶ。
整数 が与えられる。
桁の整数であって (最高次の係数は 0 でない)、 の倍数であるようなものの個数を 1000000007 で割ったあまりを求めよ。
制約
考えたこと
安直に考えると、次のような DP が良さそうに思えた。
dp[i][j][v]
← 桁の整数であって、1 の位の値が であって、 で割って あまるような整数の個数
このままだと、 として の計算量となってしまう。ちょっとでも改善したいと思うと、 のところは行列累乗を持ち出すことで に改善される。でも微妙に間に合わない...
天才的な言い換え
Increasing Number というものを天才的な言い換えをする。天才すぎる... 桁以下の Increasing Number ( 桁以下のものから 桁以下のものを引く方針でやる) とは
という形であって、
を満たすものとして特徴付けられるのだ。あとは、 の倍数であるようなものの個数を求めればよい。
DP へ
ここまで来たら、もう、すぐ!!!
num[v]
← 1, 11, 111, ... のうち、 で割って あまるものの個数
とする。ここからは次のような DP でできる。
dp[i][j][v]
← で割って あまるもののみをちょうど合計 個だけ用いて足して、全体のあまりが となるようなものの個数
遷移は次のようにできる (ただし num[i] = 0 のときは dp[i+1] = dp[i]
)。
dp[i+1][j+k][(v+i*k)%K] += dp[i][j][v] * com(k + num[i] - 1, k);
二項係数の部分は「num[i]
種類のものから k
個選ぶ」という重複組合せ。
計算量は まで改善する。
コード
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; long long modinv(long long a, long long mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a/b; a -= t*b; swap(a, b); u -= t*v; swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } long long com(long long N, long long R) { if (N < 0 || R < 0 || R > N) return 0; long long ue = 1, shita = 1; for (int k = 0; k < R; ++k) { ue = ue * ((N-k) % MOD) % MOD; shita = shita * (k+1) % MOD; } return ue * modinv(shita, MOD) % MOD; } long long solve(long long D, long long K) { if (D == 0) return 1; deque<long long> num(K, 0), syu, used(K, 0); long long v = 1 % K; for (long long i = 0; i < D; ++i) { if (used[v]) { while (!syu.empty() && syu[0] != v) { --D; ++num[syu[0]]; syu.pop_front(); } break; } syu.push_back(v); used[v] = 1; v = (v * 10 + 1) % K; } long long q = D / syu.size(), r = D % syu.size(); for (auto v: syu) num[v] += q; for (int i = 0; i < r; ++i) ++num[syu[i]]; vector<vector<long long>> dp(10, vector<long long>(K, 0)); dp[0][0] = 1; for (int i = 0; i < K; ++i) { if (!num[i]) continue; vector<vector<long long>> nex(10, vector<long long>(K, 0)); vector<long long> coms(10); for (int k = 0; k <= 9; ++k) coms[k] = com(k+num[i]-1, k); for (int j = 0; j <= 9; ++j) { for (int v = 0; v < K; ++v) { if (dp[j][v] == 0) continue; for (int k = 0; j+k <= 9; ++k) { int nv = (v + i * k) % K; nex[j+k][nv] += dp[j][v] * coms[k] % MOD; nex[j+k][nv] %= MOD; } } } swap(dp, nex); } long long res = 0; for (int i = 0; i <= 9; ++i) res = (res + dp[i][0]) % MOD; return res; } class IncreasingNumber { public: long long countNumbers(long long D, int K) { long long res = (solve(D, K) - solve(D-1, K) + MOD) % MOD; return res; } };