Luogu2481 SDOI 2010 코드 경매 DP, 콤보

전송문
신선DP
\(N\leq 10^ {18}\) 를 알아차리면 직접 디지털 DP를 사용할 수 없기 때문에 형성된\(N\) 비트의 성질을 고려합니다.
낮은 비트는 높은 비트보다 작지 않으므로 조건에 맞는 모든\(N\) 비트는\(9\)개\(f(x)(x\in[1,N])\)의 합을 초과하지 않으며 여기서\(f(x)=\sum\limits{i=0}^{x-1}10^i\), 그리고 그 중에는 반드시\(f (N)\) 가 있습니다.
\(f (x)\\bmod\P\) 로 이루어진 수열을 고려합니다.\(f (x) = 10f (x-1) + 1\) 이기 때문에 이 수열에는\(P\) 를 초과하지 않는 순환절이 반드시 존재합니다.그러면 이 예처리를 통해\(cnt i =\sum\limits {x=1}^N[f(x)\mod P = i]\) 를 미리 처리하고\(f(N)\\\bmod\P\) 의 값을 구할 수 있습니다.
다음에 DP를 사용할 수 있습니다. 설정\(f {i, j, k}\) 는\(cnt 0\sim cnt {i-1}\) 를 고려하고\(k\) 개\(f (x)\) 를 선택했습니다. 그것들의 합\(\bmod\P = j\) 방안 수입니다.이동은 열거\(cnt i\) 중 몇 개를 선택해야 하는지를 고려한다. 이것이 바로 삽입법이고 이동 계수는 하나의 조합수이다.
마지막 답은\(\sum\limits {i=0}^8 f {P,(P-f(N))\\bmod P,i}\)입니다.\(i\)가 최대\(8\)인 이유는\(f(n)\)를 선택해야 하기 때문입니다.

#include
using namespace std;

#define int long long
const int MOD = 999911659;
int dp[503][503][9] , Cnt[503] , dir[503] , N , P;

int poww(int a , int b){
    int times = 1;
    while(b){
        if(b & 1) times = times * a % MOD;
        a = a * a % MOD; b >>= 1;
    }
    return times;
}

int binom(int a , int b){
    int times = 1;
    for(int i = a ; i > a - b ; --i)
        times = times * i % MOD * poww(a - i + 1 , MOD - 2) % MOD;
    return times;
}

signed main(){
    cin >> N >> P;
    int cur = 1 % P , cnt = 1 , tmp = 1 % P , ed;
    do{dir[cur] = cnt; ++cnt; cur = (cur * 10 + 1) % P;}while(!dir[cur]);
    for(int i = 1 ; i < dir[cur] && i <= N ; ++i , tmp = (tmp * 10 + 1) % P) ++Cnt[ed = tmp];
    if(dir[cur] <= N){
        for(int i = dir[cur] ; i < cnt ; ++i , tmp = (tmp * 10 + 1) % P) Cnt[ed = tmp] = (N - dir[cur] + 1) / (cnt - dir[cur]) % MOD;
        for(int i = 1 ; i <= (N - dir[cur] + 1) % (cnt - dir[cur]) ; ++i , tmp = (tmp * 10 + 1) % P) ++Cnt[ed = tmp];
    }
    dp[0][0][0] = 1;
    for(int i = 0 ; i < P ; ++i)
        for(int j = 0 ; j <= 8 ; ++j){
            int val = binom(Cnt[i] + j - 1 , j);
            if(!val) continue;
            for(int k = 0 ; k < P ; ++k)
                for(int l = 0 ; l + j <= 8 ; ++l)
                    dp[i + 1][(k + i * j) % P][l + j] = (dp[i + 1][(k + i * j) % P][l + j] + val * dp[i][k][l]) % MOD;
        }
    int sum = 0;
    for(int i = 0 ; i <= 8 ; ++i)
        sum = (sum + dp[P][(P - ed) % P][i]) % MOD;
    cout << sum;
    return 0;
}