代码拍卖会
题意
问有[ L - R ]有多少个数满足每一位都至少有 1，从左到右不减同时要能被P整除，位数<=\(1e18\). p<=500)
思路
- 位数贼大，基本上别想着枚举有关位数的东西
- 单调不减，说明什么，说明一个合法的方法我前面的 +1 后面的至少要 +1 ，如果把他们看成最多 9个 长度为 n的01串的和，其中这些串满足 后缀全是1。这样可以保证满足条件的情况下，还能保证单调不减。
- 现在问题再处理 长度为n的01串怎么处理，因为根本不可能把他枚举出来，但是这个最后要满足是P的倍数，所以我们加上一个 11 %2 和 1 %2 的意义其实是一样的，考虑把 mod P 相同的归为一类，最后把选择一个P的情况归为在 K 个中挑X的方案数，K是在mod P意义下相同的个数。
找循环节
int c=1%p;//C是当前的 后缀情况 1 11 111 1111
int cnt=1;//没啥用
c2[0]=1%p;// 循环节中第i个位置
vis[1%p]=0;// 表示 某个后缀在循环中的位置
for(int i=1;;i++)
{
c2[i]=(c2[i-1]*10+1)%p;//每次在后面填一个1 记得取mod
if(vis[c2[i]]!=-1)//如果出现过。就准备break
{
for(int j=0;j<min(i,n);j++)g[c2[j]]++,f=c2[j];//把当前循环节的数目+1
// F是 全部是1的情况，因为要保证他每一位起码是1 ，
//所以我循环中的最后一个有一定可能是全是1 的情况，如果没有循环节的话。
//因为他可能i大于n 就是找到循环的情况比n的长度还长。
n-=i;//因为 已经加了i个的情况了，
st=vis[c2[i]];//st 表示初始也就是 第一次出现两次的情况
m=(i-st);// 这个是循环节长度，
break;
}
vis[c2[i]]=i;//标记一下 当前后缀是第几个出现的。
}
预处理G数组
n=max(0ll,n);
int time=n/m;
// m是循环节的长度
for(int i=0;i<m;i++)
{
g[c2[i+st]]+=time;
// 找到循环节 一次性全加上
}
int mod2=n%m;//把多余的部分暴力加上1
for(int i=0;i<mod2;i++)
{
g[c2[i+st]]++;
f=c2[st+i];
//这个地方，只要我找到最后的一个情况，那么这个肯定就是 全是1的情况。
}
for(int i=0;i<p;i++)g[i]%=mod;
Dp状态定义
\(D[i][j][k]\)表示当前已经选到了 mod P等于 i 的位置，同时选了 j 个 同时 mod p 等于 k 的方案数。
// 为啥要倒过来捏。因为 如果你是正着来，你mod p等于0的情况需要用到，但是你很难处理，所以索性倒过来处理。
枚举当前选了j个同时是由 (0-(i-1))中选出 j2 个转移过来的。
d[i][j2+j][k+(j2*i)%mod]=d[i+1][j2][k]*C(从 g[i] 个中选出j2个的方案数)。
然后就结束了。
Code
const int N=600,mod=999911659;
int lowbit(int x){return x&-x;}
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int d[N][10][N];
//表示当前已经选到了 mod P等于 i 的位置，同时选了 j 个 同时 mod p 等于 k 的方案数。
int g[N];//mod p 等于 i 的方案数
int vis[N];//一个后缀在循环节中出现的位置
int c2[N];//第i个后缀的值
int qmi(int x,int k)
{
int res=1;
while(k)
{
if(k&1)res=res*x%mod;
k>>=1;
x=x*x%mod;
}
return res;
}
int C(int a,int b)
{
if(a<b)return 0;
int down=1,up=1;
for(int i=a,j=1;j<=b;j++,i--)
{
up=up*i%mod;
down=down*j%mod;
}
return up*qmi(down,mod-2)%mod;
}
void solve()
{
int n,p;cin>>n>>p;
memset(vis,-1,sizeof vis);
int f=0;
int st=0,m=0;
int c=1%p;
int cnt=1;
c2[0]=1%p;
vis[1%p]=0;
int c=1%p;//C是当前的 后缀情况 1 11 111 1111
int cnt=1;//没啥用
c2[0]=1%p;// 循环节中第i个位置
vis[1%p]=0;// 表示 某个后缀在循环中的位置
for(int i=1;;i++)
{
c2[i]=(c2[i-1]*10+1)%p;//每次在后面填一个1 记得取mod
if(vis[c2[i]]!=-1)//如果出现过。就准备break
{
for(int j=0;j<min(i,n);j++)g[c2[j]]++,f=c2[j];
//把当前循环节的数目+1
// F是 全部是1的情况，因为要保证他每一位起码是1 ，
//所以我循环中的最后一个有一定可能是全是1 的情况，如果没有循环节的话。
//因为他可能i大于n 就是找到循环的情况比n的长度还长。
n-=i;//因为 已经加了i个的情况了，
st=vis[c2[i]];//st 表示初始也就是 第一次出现两次的情况
m=(i-st);// 这个是循环节长度，
break;
}
vis[c2[i]]=i;//标记一下 当前后缀是第几个出现的。
}
n=max(0ll,n);
int time=n/m;
// m是循环节的长度
for(int i=0;i<m;i++)
{
g[c2[i+st]]+=time;
// 找到循环节 一次性全加上
}
int mod2=n%m;//把多余的部分暴力加上1
for(int i=0;i<mod2;i++)
{
g[c2[i+st]]++;
f=c2[st+i];
//这个地方，只要我找到最后的一个情况，那么这个肯定就是 全是1的情况。
}
for(int i=0;i<p;i++)g[i]%=mod;
// 当前美枚举到第i位 ,用了j个 同时余数为k的
// cout<<f<<endl;
d[p+1][0][f]=1;
for(int i=0;i<p;i++)
{
for(int j=0;j<9;j++)
{
for(int s=0;s+j<9;s++)
{
int mul=C(g[i]+s-1,s);
if(!s)mul=1;//emm 从0个中选出0个在这里是合法的。
for(int d2=0;d2<p;d2++)
{
d[p-i][j+s][(d2+s*i)%p]=(d[p-i][j+s][(d2+s*i)%p]+mul*(d[p-i+1][j][d2])%mod)%mod;
}
}
}
}
int ans=0;
for(int i=0;i<9;i++)
{
ans=(ans+d[1][i][0])%mod;//最后只要看选了几个就可以了。
}
cout<<ans<<endl;
}
signed main()
{
kd;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}