香港sbp钱币拍卖，bzoj1974 [Sdoi2010]代码拍卖会 循环+背包

一般这种计数题就两个套路：找到倍数然后删除不合法的   找到合法的然后删除不是倍数的

如果先找倍数，那不合法的数位置和倍数没有直接关系

这个题是要先找合法的 然后删除不是倍数的

首先这个合法的数找的方法最传统的是数位dp，但显然不行，如果考虑对数位dp进行优化的话，也无非是矩乘之类的过程优化

香港sbp钱币拍卖？所以必须考虑转移优化，剪枝就是只循环比上一位大的，然后套用前缀和

但这样的剪枝也是没用的，由于n的特殊性，在枚举数位的时候就要离散了

由于数位dp是万能算法，不是专一算法，所以应考虑根据题目进行变动

题目是要求升序，是一个对行的要求，虽然列是1e18，但行里的数字只有可能是单调的1~9，考虑按行做

然后就考虑这个数列在哪个位置改数 最多改9处，然后就相当于给一个从起点到指定位置+1；

stackbowers拍卖。所以就相当于+1 +11 +111 +1111……

然后就考虑用这些数字怎么构成k的倍数就可以了，用类似循环节的处理方法就可以了

主要就是要知道优化的最重要的就是去除重复，所以需要找到问题求解中重复的部分，换角度找重复的部分，想办法构造重复的部分，重复的部分还有很多（如加换乘，枚举换背包、循环化除、枚举化二分、扫描无用化单调队列……）离散后直接用数学或基本模型

码：

#include<iostream>
#include<cstdio>
using namespace std;
long long P=999911659;
#define ll long long
ll i,j,n,K,l,k,ni[11],C[505][15],f[15][505],g[15][505],x,y,s,cnt[505],len,wz[505],qd,ans,v[505];
void exgcd(ll a,ll b)
{if(!b){x=1;y=0;return; }exgcd(b,a%b);ll t=x;x=y;y=t-(a/b)*y;
}
int main()
{
scanf("%lld%lld",&n,&K);ni[1]=1;for(i=2;i<=9;i++)exgcd(i,P),ni[i]=(x+P)%P;
if(K==1)
{ans=1;for(i=1;i<=8;i++){ans=ans*((n+i)%P)%P*ni[i]%P;}printf("%lld",ans);return 0;
}
if(n<K)
{for(i=1;i<=n;i++)
{s=(s*10+1)%K;cnt[s]++;	
}	
}else
{
for(i=1;i<=K+1;i++)
{s=(s*10+1)%K;if(cnt[s]){len=i-wz[s];//周期 	qd=wz[s];break;}wz[s]=i;v[i]=s;cnt[s]++;	
}	
for(i=qd;i<=qd+len-1;i++)cnt[v[i]]=0;
for(i=qd;i<=qd+len-1;i++)//普及周期 {cnt[v[i]]+=((n-qd+1)/len);if((n-qd+1)%len!=0&&(n-qd+1)%len>=i-qd+1)cnt[v[i]]++;cnt[v[i]]%=P;}
if((n-qd+1)%len==0)s=v[qd+len-1];
else s=v[qd+(n-qd+1)%len-1];
}for(i=0;i<K;i++){C[i][0]=1;for(j=1;j<=9;j++)C[i][j]=C[i][j-1]*(cnt[i]+j-1)%P*ni[j]%P;}	
f[1][s]=1;for(j=0;j<K;j++)//要加哪一个 {for(i=0;i<K;i++)//当前余数	for(k=1;k<=9;k++) //当前几个 for(l=0;l<=9-k;l++)//要加几个 {g[k+l][(i+j*l%K)%K]+=f[k][i]*C[j][l]%P;g[k+l][(i+j*l%K)%K]%=P;}for(k=0;k<K;k++)for(i=0;i<=9;i++){f[i][k]=g[i][k];g[i][k]=0;}}
for(i=1;i<=9;i++)
ans+=f[i][0],ans%=P;
printf("%lld",ans);
}