题解 P2481 【[SDOI2010]代码拍卖会】

Imakf · 2020-01-13 22:06:50 · 题解

题意转化

本题的转化非常妙妙！

对于任何一个猪猪举牌的方案，都可以看做 9 个以内的若干 “1 的后缀”相加而成！

感性理解如下图：

于是我们把一个方案拆成了若干的形如 00000...11111 的数字相加！

题目中让我们求 \mod p 意义下为 0 的方案数。

想想怎么做？

我们可以把一个数分割成若干个 000000...11111 的和。

所以我们可以计算出 n 个 “1 的后缀”在 \mod p 意义下的值。

因为可以选至多 9 种后缀，所以就可以跑 O(n^9) 暴力！

~~然而这一个点都过不去啊~~

其实我们可以直接把 \mod p 意义下有相同数值的后缀看成同一类

比如 11 和 1 在 \mod 5 意义下是同一类。

不妨记 g[i] 为 \mod p 意义下[余数是 i 的“1 的后缀”]的数量。

(最后再讲 g[i] 的求法，想看可以直接跳)

我们就可以不用暴力

而是做一个背包的转移就好了！

背包

设 dp[i][j][s] 表示当前考虑到余数为 i 的 “1 的后缀”，此前已经放上了 j 个“1 的后缀”，此时构成的数字的 \mod p 的余数是 s 的方案数。

枚举“1 的后缀”\mod p 意义下的余数 O(p)，记为 i。

枚举当前已经铺了几个“1 的后缀”。O(9)，记为 j。

为什么是 O(9)，因为最左边的猪是不能出价为 0 的，所以最初要强制铺一层全 1。

枚举当前这种 “1 的后缀”铺了几个。O(9)，记为 s。

枚举转移过来的状态\mod p 意义下的余数。O(p)，记为 d。

则转移方程是：

dp[p][s+j][(d+s*i+p)\%p]+=\sum\limits \dbinom{g[i]+s-1}{s}dp[p-1][j][d]

这个 \dbinom{g[i]+s-1}{s} 是什么呢？

就是在 g[i] 中选 s 个同种 “1 的后缀”有多少种不同的方法！

证明即隔板法。

复杂度即 O(81p^2)

至于怎么计算这个组合数，直接按定义计算就好。

循环节的计算

那么怎么计算 g[] 数组呢？

~~普及组知识？~~

定义 s_i 表示 i 个 1 连起来形成的数, f_i 为它在 \mod p 意义下的值。

如 s_5=11111

f_3=1\mod 5

则显然有 f_i=(10\times f_{i-1}+1)\%p

显然这柿子在 2p 次迭代内必然会出现循环。

可以把 f_i 分成三段：

未进入循环段
循环段
不完整循环段

暴力统计未进入和不完整的，用循环节搞定循环的就好了。

代码如下：

#include <cstring>
#include <iostream>
using namespace std;

#define mod (999911659LL)
#define MX (500 + 5)
#define LL long long

LL qpow(LL x ,LL y ,LL P){
    if(!y)  return 1;
    if(y == 1)  return x;
    LL t = qpow(x ,y >> 1 ,P);
    if(y & 1)   return t * t % P * x % P;
    return t * t % P;
}
LL g[MX] ,n ,p ,cycLen ,cycstNum;
int cycle[MX * MX] ,first[MX];
LL dp[MX][11][MX];
LL C(LL n ,LL m){
    if(m < 0)   return 0;
    LL fz = 1 ,fm = 1;
    for(int i = 0 ; i < m; ++i){
        (fz *= n - i) %= mod;
        (fm *= m - i) %= mod;
    }
    return fz * qpow(fm ,mod - 2 ,mod) % mod;
}

int main(){
    // cout << C(10 ,7);
    memset(first ,-1 ,sizeof first);
    cin >> n >> p;
    cycle[0] = 1 % p;
    first[1 % p] = 0;
    LL addition = 0;
    // first 是该数第一次出现的位置
    // cycle 是按顺序出现的数 %p
    for(int i = 1 ; ; ++i){
        cycle[i] = (cycle[i - 1] * 10 + 1) % p;
        if(~first[cycle[i]]){
            for(int j = 0 ; j < i && j < n; ++j)
                g[cycle[j]]++ ,addition = cycle[j];
            n -= i;
            cycstNum = cycle[i];
            cycLen = i - first[cycle[i]];
            break;
        }
        first[cycle[i]] = i;
    }
    n = max(n ,0LL);
    LL times = n / cycLen;
    for(int i = 0 ; i < cycLen ; ++i)
        g[cycle[i + first[cycstNum]]] += times;
    LL nn = n % cycLen;
    for(int i = 0 ; i < nn ; ++i)
        g[cycle[i + first[cycstNum]]]++ ,addition = cycle[i + first[cycstNum]];
    for(int i = 0 ; i < p ; ++i)    g[i] %= mod;

    // 因为我很懒，按照上文博客
    // 在计算 dp[0][][] 的时候会调用 dp[-1][][] 导致 RE
    // 所以我是倒着来的，把 dp[0] 变成 dp[p] ，dp[1] 变成 dp[p - 1]...
    dp[p + 1][0][addition] = 1;
    // 此处 addition 是强制要求选择一次全 111111... 造成的代价
    for(int i = 0 ; i < p ; ++i){   // 枚举使用的 0000...1111 %p 意义的值  
        for(int j = 0 ; j < 9 ; ++j){   // 枚举已经使用次数 
            for(int s = 0 ; s + j < 9 ; ++s){   // 枚举当前使用次数 
                LL multi = C(g[i] + s - 1 ,s);
                for(int d = 0 ; d < p ; ++d){   // 枚举已经的余数 
                    // if(dp[p - i + 1][j][d]){printf("dp[%lld][%d][%lld] += multi(%lld) * dp[%lld][%d][%d](%lld);\n" ,p - i ,s + j ,(d + s * i) % p ,multi ,p - i + 1 ,j ,d ,dp[p - i + 1][j][d]);}
                    (dp[p - i][s + j][(d + s * i) % p] += multi * dp[p - i + 1][j][d]) %= mod;
                }
            }
        }
    }
    LL Ans = 0;

    for(int i = 0 ; i < 9 ; ++i){
        (Ans += dp[1][i][0]) %= mod;
    }

    cout << Ans << endl;
    return 0;
}

```