网站建设mfdos 优帮云外国设计师素材网站

题解前的BB
题目居然用漫作为题目背景，题目中那神说的话不符合语法，我也是醉了。

题目大意
给出$n,m(0\le n\le 10^{18},1\le m\le 100)$，有序列$a_1,a_2,a_3...a_{k-1},a_k$满足这些数的和是n，且每个数模m后的结果互不相同，求这样的序列的个数，结果模905229641。

我们先来学习一些必备的东西。

放小球问题
现在我们来考虑一类特殊的问题：现在有a个球，要将其分成b组，每组至少有一个球，求方案数。
我们把$a$个球摊开后，题目就变成，要在a个格子之间放b-1个隔板（即在$a-1$个空隙中放入$b-1$隔板），使其分成b组，那么这样的组合数就为$C_{a-1}^{b-1}$

这个问题再升级一下就变成：现在有$a$个球，要将其分成$b$组，每组可以没有球，求方案数。
这样的解法其实是类似的。
考虑一个合法的方案，在每一组里都加入一个球，则每一组都有至少一个球，就得球的个数就变成了$a+b$个，题目就变成了：有$a+b$个球，要将其分成b组，每组至少有一个球，求方案数。则由上面一个问题的结论得出，这个问题的答案即为$C_{a+b-1}^{b-1}$。

逆元
大家都知道倒数吧，$\frac {1}{x}$是$x$的倒数，那么在模意义下的倒数即为逆元，即如果满足$x\times x' \equiv 1\pmod p$，那么$k$就是$x$的逆元，
由费马小定理：当$x$与$p$互质时，$x^{p-1}\equiv 1\pmod p$
得$x\times x^{p-2}\equiv 1\pmod p$
又因为$x\times x' \equiv 1\pmod p$
那么$x'\equiv x^{p-2}\pmod p$
即$x$的逆元为$x^{p-2}$

思路
一个很直观的想法是设$f_{x,y}$表示这个序列的数的和是x,有y个模m后结果不同的数的方案数，显然转移伪代码为

t=0 -> m-1k=0 -> nif k%t==0x=n -> 0y=1 -> mf[x][y]=f[x][y]+f[x-k][y-1];

算出$f$数组后直接统计答案就好了。
然而，这样的时间复杂度是$O_{(n^2m^2)}$，显然很暴力，空间也很大。
这个方程是可以优化的！！！,设$f_{x,y}$表示这个序列的数模m后的和为x,有y个模m后结果不同的数的方案数，这样的话，转移就变成了

t=0 -> m-1x=m*(m-1)/2 -> 0y=1 -> mf[x][y]=f[x][y]+f[x-t][y-1];

这样的时间复杂度就变成了$O_{(m^4)}$，时限一秒，可以过。但是，还没有完，我们还要求答案。

回归题目
前面我们已经预处理出了$f$数组，然后在于处理出$js_i$表示$i$的阶乘。设有序列$b_1,b_2...b_k$满足$b$序列的数互不相同且都小于m，求答案的具体思路就是枚举$b$序列的和$t$，显然我们可以得出还需给任意一些$b$序列里的数加上共$((n-t)\div m)$个m，就能使$b$序列成为一个合法的$a$序列，设$x=(n-t)\div m$，再枚举$b$序列的长度$len$，那么再由前面讨论出的特殊问题的结论（看到这里读者也许忘了，就是将a个球分成b组，每组可以没有球的方案数为$C_{a+b-1}^{b-1}$），答案就为$f_{t,len}*js_{len}*C_{x+len-1}^{len-1}$的和
看到这儿，是不是觉得这就是正解，小心脏就兴奋了？快要炸开了？太天真了。
由数据范围$(0\le n\le 10^{18})$，$x$的值可能很大，所以组合数不可以直接预处理，怎么办？因为$len$是从1到m枚举的，所以当$len=1$时，组合数的值为1，于是我们可以一个一个转移组合数的值。
当我们从$C_{x+len-1}^{len-1}$转移到$C_{x+len}^{len}$时，实际上，$C_{x+len}^{len}=C_{x+len-1}^{len-1}\times \frac{x+len}{len}$
因为有模，所以要用逆元，所以
$C_{x+len}^{len}\equiv C_{x+len-1}^{len-1}\times (x+len)\times len^{p-2}\pmod p$
于是就可以完美解决了，除预处理外时间复杂度$O_{(m^3)}$

下面附一下代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<cstring>
#include<queue>
#include<functional>
#include<set>
#include<map>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)typedef long long LL;
const int mod = 905229641;
const int M = 110;using namespace std;LL n;
LL m,f[M][M*M],ans,js[M];void prepare(){f[0][0]=1;fo(i,0,m-1)fd(x,i,0)fo(y,0,m*(m-1)/2-i)if (f[x][y])f[x+1][y+i]=(f[x][y]+f[x+1][y+i])%mod;js[1]=1;fo(i,2,m)js[i]=js[i-1]*i%mod;
}LL quickmi(LL x,int tim){LL ans=1;while (tim){if (tim%2==1)ans=(ans*x)%mod;x=(x*x)%mod;tim/=2;}return ans;
}void getans(){ans=0;fo(i,0,m*(m-1)/2)if ((n-i)%m==0){LL x=((n-i)/m)%mod;LL tot=1;fo(j,1,m){ans=(ans+f[j][i]*js[j]%mod*tot%mod)%mod;tot=(tot*(x+j)%mod*quickmi(j,mod-2)%mod)%mod;}   }
}int main(){scanf("%lld%d",&n,&m);prepare();getans();printf("%lld\n",ans);
}