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

· · 题解

solution:

这道题调了好久好久，久到都要放弃了。洛谷的第五个点是真的强，简简单单一个1，调了快4个小时！

这道题第一眼怎么都是数位DP，奈何数据范围太大，只能找性质。而这道题最重要的一个性质也很套路（敲难想），因为我们所有的方案都是 111112223333 这样的数，我们要求的是它的大小模 p ，所以我们考虑将它用加法拆解。于是我们惊奇的发现它可以转化成（以上面那个数为例） 111111111111+1111111+1111=111112223333 。正因为数位上的数字单调不降，所以它可以表示为不超过9个形似 111...111 的数的和！

而这种形似 1111...1111 的数，我们可以发现，如果我们依次枚举它的长度（ 1,11,111,1111...... ）这些数在模 p 意义下一定会产生循环节。于是我们将在模 p 意义下同余的这类数归到一起，然后用一个数组 g[i] 记录模 p 意义下为 i 的形如 11111...111 的数的个数。（因为 p 不大，所以不用枚举多久就能找到循环节）

于是题目的意思就被转换成：从所有的 g[i] 中找出（不超过）九个数，使得它们的下标之和能被 p 整除！（为什么是下标之和？因为上面说了 g[i] 中所有的形如 1111...111 的数在模 p 意义下为 i ！）

所以这道题就变成了一道计数类DP，我们设 f[i][j][o] 表示：已经选完了下标为 [0,i-1] 的数，从中选了 o 个形如 1111...11 的数，它们的和模 p 等于 j 的方案数。 考虑它的转移，如果我们要从下标为 i 的数里选出 k 个数，显然这 k 个数是可以重复的，他们的贡献都为 i ，所以相当我们从 g[i] 个数里可重复的选出 k 个数（不论怎么选他们的和都为 k*i ），根据组合计数原理这样的方案有 C_{g[i]+k-1}^{~~~~~k} 种。为了方便博主代码里会用 C[i][k] 代替 C[~g[i]+k-1~][k] 。

f[i+1][~(j+k*i)~mod~p~][o+k]=f[i][j][o]*C[i][k]

code: 

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define rg register int

using namespace std;

const int mod=999911659; //答案的模数

ll n;
ll g[505]; //记录余数为i的形如11111的数的个数
int p,vn,ans; //循环节长度，小模数
int a[505]; //记录余数上一次的位置（找循环节用）
int inv[11]; //逆元
int c[505][11]; //组合数
int f[505][505][11]; //计数类DP

inline int qr(){
    register char ch; register bool sign=0; rg res=0;
    while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
    while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
    if(sign)return -res; else return res;
}

int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%d",&n,&p); inv[1]=1;
    if(n<=p) for(rg i=1;i<=n;++i) vn=(vn*10+1)%p,++g[vn];
    else{ rg tot=1%p,m,l;
        for(rg i=1;i<=p+1;++i){
            if(a[tot]){ l=a[tot]; m=i-l; break;} //找到循环节，计算循环节长度
            a[tot]=i; ++g[tot]; tot=(tot*10+1)%p; //记录当前余数出现位置，继续寻找
        }
        for(rg i=0;i<p;++i)
            if(a[i]&&a[i]>=l){
                g[i]+=(n-a[i])/m%mod; //记录所有余数为i的形如11111的数的个数
                if((a[i]-l+1)%m==(n-l+1)%m) vn=i; //记录长度为 n 的形如1111的数的余数，后面初始DP时有用
            }
    }
    for(rg i=2;i<9;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; //线性递推求逆元
    for(rg i=0;i<p;++i){ c[i][0]=1; if(!g[i])continue;
        for(rg j=1;j<9;++j,g[i]=(g[i]+1)%mod) //注意最后还有个++g[i]！！！
            c[i][j]=(ll)c[i][j-1]*g[i]%mod*inv[j]%mod; //用性质求i较大,j较小的逆元
    }
    f[0][vn][0]=1; //最开始有一个长度为n的形如1111111111的数
    for(rg i=0;i<p;++i)
        for(rg j=0;j<p;++j)
            for(rg o=0;o<9;++o)
                for(rg k=0;k<9-o;++k) //枚举取出多少个余数为i的形如的11111111的数
                    (f[i+1][(j+k*i)%p][k+o]+=(ll)f[i][j][o]*c[i][k]%mod)%=mod;
    for(rg i=0;i<9;++i) ans=(ans+f[p][0][i])%mod; //计算答案
    printf("%d\n",ans);
    return 0;
}