P2481 [SDOI2010]代码拍卖会 (dp)

题意：求长度为n的数，每一位不比前一位小，且可以被P整除的数的个数
题解：可以看成在1,11,111.......，111..（n个1）里面取9个（可重复）
dp[i][j][k]表示%p=i-1的数已经取过了，共取了k个数，当前%p=j
cnt[i]表示%p=i的数有i个，在cnt[i]里面取j个，因为cnt[i]个数里面每个数都有无穷个，所以组合数为c[cnt[i]+j-1][j]
转移见代码

#include<stdio.h>
#define ll long long
#define mod 999911659
ll dp[510][510][15];
ll cnt[510],vis[510],inv[10];
ll quickpow(ll a,ll b){
	ll ans=1;
	while(b!=0){
		if(b%2==1)ans=(ans%mod*a%mod)%mod;
		a=(a%mod*a%mod)%mod;
		b=b/2;
	}
	return ans;
}
ll getc(ll a,ll b){
	if(a<b)return 0;
	ll ans=1;
	for(ll i=1;i<=b;i++){
		ans=(a-i+1)%mod*inv[i]%mod*ans%mod;
	}
	return ans;
}
int main(){
	inv[1]=1;
	for(int i=2;i<=9;i++)inv[i]=quickpow(i,mod-2);
	ll n,p;
	scanf("%lld %lld",&n,&p);
	int cs=0,zq=0;
	int now=1;
	ll inite;
	for(int i=1;i<=n;i++){
		if(cnt[now%p]!=0){
			cs=vis[now%p];
			zq=i-vis[now%p];
			break;
		}
		cnt[now%p]++;
		vis[now%p]=i;
		if(i==n)inite=now%p;
		now=(now*10+1)%p;
	}
	if(zq!=0){
		for(int i=0;i<p;i++){
			if(cnt[i]!=0&&vis[i]>=cs){
				cnt[i]=(n-vis[i])/zq+1;
				if((n-vis[i])%zq==0){
					inite=i;
				}
			}
		}
	}
	//printf("%d\n",inite);
	dp[0][inite][0]=1;
	for(int i=0;i<p;i++){
		//printf("cnt[%d]=%lld\n",i-1,cnt[i-1]);
		for(int j=0;j<p;j++){
			for(int k=0;k<9;k++){
				dp[i+1][j][k]=dp[i][j][k];
				for(int h=1;h<=k;h++){
					dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][((j-h*i)%p+p)%p][k-h]*getc(cnt[i]+h-1,h))%mod;
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=8;i++)ans=(ans+dp[p][0][i])%mod;
	printf("%lld\n",ans);
} 

P2481 [SDOI2010]代码拍卖会 (dp)

原文：https://www.cnblogs.com/League-of-cryer/p/14199722.html