§P2481 [SDOI2010]代码拍卖会 题解
题目链接：洛谷
用1~9这些数位，组成一个n位的正整数，满足从左到右，每一位的数值都不小于上一位数字，且能正好被P整除。求有多少种方案。答案mod 999911659。
§题目转化
首先，我们要对题目要求的nn位且每位递增的数，进行如下改造：
假设原数是112224456667889，
112224456667889
=111111111111111
1111111111111
1111111111
1111111111
11111111
1111111
1111
111
+ 1
------------------
112224456667889
没错，就是把原数拆成小于等于9个的$11..1$相加。
因为一个数模$p$只有$p$种情况，于是我们将这些连续的$1$按照除$p$余数的归类。
我们定义$cnt_i$表示模$p$意义下等于$i$的连续$1$的个数。
下面说一下$cnt_i$的求法：
定义$f_i$表示长度为$i$的连续1的数除$p$的余数。
那么$f_{i+1}=(f_i\times10+1)%p$ ，很显然这个余数是有循环节的，我们求出前$2p$个$f_i$即可找到循环节，之后在$n$的范围内统计即可。
§DP求解
定义$dp[i][j][k]$表示在前$i$种连续1的串中（模数为$i$），选择$j$个，使他们的和的模数是$k$的方案数。
考虑转移，现在我们已经知道$dp[i][j][k]$了，枚举第$i+1$种数我们选择多少个，假设选了$l$个。
那么，$dp[i+1][j+l][(k+(i+1)\times l)%p]+=dp[i][j][k]\times multiple$
这里的$multiple$表示在$cnt_{i+1}$个中，选$l$个，可重复选的方案数。
§组合计数
上面的这个$multiple$咋求呢？插板法。
具体的，我们有$l$个小球，要分成$cnt_{i+1}$堆，那么第$i$堆里的小球数表示第$i$种串选几个。
由于可以不选，即多个板子插到一个空，所以我们先将小球数增加$cnt_{i+1}$个，选完之后每堆拿走一个，这就是可以不选的情况。
现在我们有$l+cnt_{i+1}$个小球，在其中插$cnt_{i+1}-1$个板子，答案为$C_{l+cnt_{i+1}-1}^{cnt_{i+1}-1}=C_{l+cnt_{i+1}-1}^{l}$，这里组合数的求法可以看代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P=1010,Mod=999911659;
ll n,cnt[P];
ll p,lst_mod;
ll pos[P],mod[P<<1];
void find_red(){//找循环节
ll k=1%p;
for(int i=1;i<=2*p;i++){
mod[i]=k;
if(pos[k]){
ll len=i-pos[k];
ll bl=(n-(pos[k]-1))/len;
for(ll j=1;j<pos[k]&&j<=n;j++) cnt[mod[j]]=1,lst_mod=mod[j];//暴力循环节前面的
for(ll j=pos[k];j<i;j++) cnt[mod[j]]=bl,lst_mod=mod[j];//循环节内的球答案
for(ll j=pos[k];len*bl+j<=n;j++) cnt[mod[j]]++,lst_mod=mod[j];//最后没满一个循环节的
break;
}
pos[k]=i;//第一次出现这个余数的位置
k=k*10+1;k%=p;//f[i]
}
}
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%Mod;
y>>=1;x=x*x%Mod;
}
return ans;
}
ll C(ll x,ll y){
ll r=1,l=1;
for(ll i=1;i<=y;i++){
l=l*i%Mod;
r=r*((x-i+1)%Mod)%Mod;
}
return r*qpow(l,Mod-2)%Mod;
}
ll dp[P][20][P];
int main(){
cin>>n>>p;
find_red();
for(int i=0;i<=8;i++) //这个是初始化
//我们要保证n位，于是把长度为n的串垫在了底下，所以初始时，模数为长度为n的1串的模数。
dp[0][i][lst_mod]+=C(i+cnt[0]-1,i),
dp[0][i][lst_mod]%=Mod;
for(int i=0;i<p;i++){
for(int j=0;j<=8;j++){
for(int l=0;l+j<=8;l++){
//这里我们要变一下循环的顺序，先l再k，以免重复求multiple导致TLE。
ll multiple=C(l+cnt[i+1]-1,l);
for(int k=0;k<p;k++){
dp[i+1][j+l][(k+l*(i+1)%p)%p]+=dp[i][j][k]*multiple%Mod;
dp[i+1][j+l][(k+l*(i+1)%p)%p]%=Mod;
}
}
}
}
ll ans=0;
for(int i=0;i<=8;i++)
ans=(ans+dp[p-1][i][0])%Mod;
cout<<ans;
}
|