涪陵区小城镇建设管理处网站,如何查找同行网站做的外链,WordPress博客Modown模板,北京高端网站制作题解前的BB 题目居然用漫作为题目背景#xff0c;题目中那神说的话不符合语法#xff0c;我也是醉了。
题目大意 给出 n,m(0≤n≤1018,1≤m≤100) #xff0c;有序列 a1,a2,a3...ak−1,ak 满足这些数的和是n#xff0c;且每个数模m后的结果互不相同#xff0c;求这样的…题解前的BB 题目居然用漫作为题目背景题目中那神说的话不符合语法我也是醉了。
题目大意 给出 n,m(0≤n≤1018,1≤m≤100) n,m(0\le n\le 10^{18},1\le m\le 100)有序列 a1,a2,a3...ak−1,ak a_1,a_2,a_3...a_{k-1},a_k满足这些数的和是n且每个数模m后的结果互不相同求这样的序列的个数结果模905229641。
我们先来学习一些必备的东西。
放小球问题 现在我们来考虑一类特殊的问题现在有a个球要将其分成b组每组至少有一个球求方案数。 我们把 a a个球摊开后，题目就变成，要在a个格子之间放b-1个隔板（即在a−1a-1个空隙中放入 b−1 b-1隔板使其分成b组那么这样的组合数就为 Cb−1a−1 C_{a-1}^{b-1}
这个问题再升级一下就变成现在有 a a个球，要将其分成bb组每组可以没有球求方案数。 这样的解法其实是类似的。 考虑一个合法的方案在每一组里都加入一个球则每一组都有至少一个球就得球的个数就变成了 ab a+b个题目就变成了有 ab a+b个球要将其分成b组每组至少有一个球求方案数。则由上面一个问题的结论得出这个问题的答案即为 Cb−1ab−1 C_{a+b-1}^{b-1}。
逆元 大家都知道倒数吧 1x \frac {1}{x}是 x x的倒数，那么在模意义下的倒数即为逆元，即如果满足x×x′≡1(modp)x\times x' \equiv 1\pmod p 那么 k k就是xx的逆元 由费马小定理当 x x与pp互质时 xp−1≡1(modp) x^{p-1}\equiv 1\pmod p 得 x×xp−2≡1(modp) x\times x^{p-2}\equiv 1\pmod p 又因为 x×x′≡1(modp) x\times x' \equiv 1\pmod p 那么 x′≡xp−2(modp) x'\equiv x^{p-2}\pmod p 即 x x的逆元为xp−2x^{p-2}
思路 一个很直观的想法是设 fx,y f_{x,y}表示这个序列的数的和是x,有y个模m后结果不同的数的方案数显然转移伪代码为
t0 - m-1k0 - nif k%t0xn - 0y1 - mf[x][y]f[x][y]f[x-k][y-1];
算出 f f数组后直接统计答案就好了。
然而，这样的时间复杂度是O(n2m2)O_{(n^2m^2)}显然很暴力空间也很大。 这个方程是可以优化的,设 fx,y f_{x,y}表示这个序列的数模m后的和为x,有y个模m后结果不同的数的方案数这样的话转移就变成了
t0 - m-1xm*(m-1)/2 - 0y1 - mf[x][y]f[x][y]f[x-t][y-1];
这样的时间复杂度就变成了 O(m4) O_{(m^4)}时限一秒可以过。但是还没有完我们还要求答案。
回归题目 前面我们已经预处理出了 f f数组，然后在于处理出jsijs_i表示 i i的阶乘。设有序列b1,b2...bkb_1,b_2...b_k满足 b b序列的数互不相同且都小于m，求答案的具体思路就是枚举bb序列的和 t t，显然我们可以得出还需给任意一些bb序列里的数加上共 ((n−t)÷m) ((n-t)\div m)个m就能使 b b序列成为一个合法的aa序列设 x(n−t)÷m x=(n-t)\div m再枚举 b b序列的长度lenlen那么再由前面讨论出的特殊问题的结论看到这里读者也许忘了就是将a个球分成b组每组可以没有球的方案数为 Cb−1ab−1 C_{a+b-1}^{b-1}答案就为 ft,len∗jslen∗Clen−1xlen−1 f_{t,len}*js_{len}*C_{x+len-1}^{len-1}的和 看到这儿是不是觉得这就是正解小心脏就兴奋了快要炸开了太天真了。 由数据范围 (0≤n≤1018) (0\le n\le 10^{18}) x x的值可能很大，所以组合数不可以直接预处理，怎么办？因为lenlen是从1到m枚举的所以当 len1 len=1时组合数的值为1于是我们可以一个一个转移组合数的值。 当我们从 Clen−1xlen−1 C_{x+len-1}^{len-1}转移到 Clenxlen C_{x+len}^{len}时实际上 ClenxlenClen−1xlen−1×xlenlen C_{x+len}^{len}=C_{x+len-1}^{len-1}\times \frac{x+len}{len} 因为有模所以要用逆元所以 Clenxlen≡Clen−1xlen−1×(xlen)×lenp−2(modp) C_{x+len}^{len}\equiv C_{x+len-1}^{len-1}\times (x+len)\times len^{p-2}\pmod p 于是就可以完美解决了除预处理外时间复杂度 O(m3) O_{(m^3)}
下面附一下代码
#includeiostream
#includecstdio
#includealgorithm
#includecmath
#includenumeric
#includecstring
#includequeue
#includefunctional
#includeset
#includemap#define fo(i,a,b) for(int ia;ib;i)
#define fd(i,a,b) for(int ia;ib;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[x1][yi](f[x][y]f[x1][yi])%mod;js[1]1;fo(i,2,m)js[i]js[i-1]*i%mod;
}LL quickmi(LL x,int tim){LL ans1;while (tim){if (tim%21)ans(ans*x)%mod;x(x*x)%mod;tim/2;}return ans;
}void getans(){ans0;fo(i,0,m*(m-1)/2)if ((n-i)%m0){LL x((n-i)/m)%mod;LL tot1;fo(j,1,m){ans(ansf[j][i]*js[j]%mod*tot%mod)%mod;tot(tot*(xj)%mod*quickmi(j,mod-2)%mod)%mod;} }
}int main(){scanf(%lld%d,n,m);prepare();getans();printf(%lld\n,ans);
}
