けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TopCoder SRM 452 DIV1 Hard - IncreasingNumber (本番 0 人)

SRM 埋めを始めたいと思う! ところでこの問題、こんなの気付かないよ...!! まあ、Petr と tourist も参加したコンテストで誰も AC してない問題なので...。

問題概要

10 進法表記で最高次数から順に広義単調増加であるような整数を Increasing Number と呼ぶ。

整数  D, K が与えられる。

 D 桁の整数であって (最高次の係数は 0 でない)、 K の倍数であるようなものの個数を 1000000007 で割ったあまりを求めよ。

制約

  •  1 \le D \le 10^{18}
  •  1 \le K \le 500

考えたこと

安直に考えると、次のような DP が良さそうに思えた。

  • dp[i][j][v] i 桁の整数であって、1 の位の値が  j であって、 K で割って  v あまるような整数の個数

このままだと、 G = 10 として  O(DKG^{2}) の計算量となってしまう。ちょっとでも改善したいと思うと、 i のところは行列累乗を持ち出すことで  O(K^{3}G^{3} \log D) に改善される。でも微妙に間に合わない...

天才的な言い換え

Increasing Number というものを天才的な言い換えをする。天才すぎる... D 桁以下の Increasing Number ( D 桁以下のものから  D-1 桁以下のものを引く方針でやる) とは

 1 \times x_{1}
 + 11 \times x_{2}
 + \dots
 + 11...1 \times x_{D}

という形であって、

  •  x_{i} \ge 0
  •  x_{1} + x_{2} + \dots + x_{D} \le 9

を満たすものとして特徴付けられるのだ。あとは、 K の倍数であるようなものの個数を求めればよい。

DP へ

ここまで来たら、もう、すぐ!!!

  • num[v] ← 1, 11, 111, ... のうち、 K で割って  v あまるものの個数

とする。ここからは次のような DP でできる。

  • dp[i][j][v] K で割って  0, 1, \dots, i-1 あまるもののみをちょうど合計  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 個選ぶ」という重複組合せ。

計算量は  O(K^{2}G^{2}) まで改善する。

コード

#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;
    }
};