湘潭网站建设 都来磐石网络,江苏市场监督管理局旗舰店,google网站地图,湘西吉首市建设局网站就是运用\(Lucas\)推一个柿子 首先是前置芝士\(Lucas\)定理 \[C_{n}^{m}\%pC_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p\] 至于证明 我建议去问一下Lucas本人 至于这道题#xff0c;我们要求的是这个柿子 \[\sum_{i0}^kC_{n}^i\%p\] 于是我们设\(f(n,k)\sum_{i0}^kC_{n}^i\) 我们就可以… 就是运用\(Lucas\)推一个柿子 首先是前置芝士\(Lucas\)定理 \[C_{n}^{m}\%pC_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p\] 至于证明 我建议去问一下Lucas本人 至于这道题我们要求的是这个柿子 \[\sum_{i0}^kC_{n}^i\%p\] 于是我们设\(f(n,k)\sum_{i0}^kC_{n}^i\) 我们就可以化柿子啦 \[f(n,k)\sum_{i0}^kC_{n}^i\] \[\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\sum_{i0}^kC_{n/p}^{i/p}*C_{n\%p}^{i\%p}\] 这个东西一看就很熟悉\(n/p\)啊显然跟整除分块差不多啊 \[C_{n/p}^0\sum_{i0}^{p-1}C_{n\%p}^iC_{n/p}^1\sum_{i0}^{p-1}C_{n\%p}^i...C_{n/p}^{k/p}\sum_{i0}^{k\%p}C_{n\%p}^i\] 前面有\(0\)到\(k/p-1\)这些个整块于是我们可以将\(\sum_{i0}^{p-1}C_{n\%p}^i\)提出来 变成 \[\sum_{i0}^{p-1}C_{n\%p}^i*(C_{n/p}^0C_{n/p}^1...C_{n/p}^{k/p-1})\] 那这个东西岂不是可以写成 \[f(n\%p,p-1)*f(n/p,k/p-1)\] 在加上那个不完整的块 \(\sum_{i0}^{k\%p}C_{n\%p}^i\)可以写成\(f(n\%p,k\%p)\) 于是就有 \[f(n,k)f(n\%p,p-1)*f(n/p,k/p-1)C_{n/p}^{k/p}*f(n\%p,k\%p)\] 由于\(n\%p\)还有\(k\%p\)都小于\(2333\)所以\(f(n\%p,p-1)\)还有\(f(n\%p,k\%p)\)可以直接预处理好可以直接求出来 至于那个\(C_{n/p}^{k/p}\)就直接上\(Lucas\)好了 时间复杂度\(O(p^2Tlog_{2333}^2n)\) 代码 非常sb的把\(C_0^0\)当成\(0\)WA了好几发 #includeiostream
#includecstring
#includecstdio
#define re register
#define LL long long
#define maxn 2335
const int P2333;
LL c[maxn2][maxn2];
LL f[maxn2][maxn2];
inline LL Lucas(LL n,LL m)
{if(!m) return 1;if(nm) return 1;if(nm) return 0;return c[n%P][m%P]*Lucas(n/P,m/P)%P;
}
inline LL F(LL n,LL k)
{if(k0) return 0;if(!n) return 1;if(!k) return 1;if(nPkP) return f[n][k];return (F(n/P,k/P-1)*f[n%P][P-1]%PLucas(n/P,k/P)*f[n%P][k%P]%P)%P;
}
int main()
{int T;scanf(%d,T);c[0][0]1;for(re int i1;imaxn;i) c[i][i]c[i][0]1;for(re int i1;imaxn;i)for(re int j1;ji;j)c[i][j](c[i-1][j]c[i-1][j-1])%P;f[0][0]1;for(re int i1;imaxn;i) f[i][0]1;for(re int i0;imaxn;i)for(re int j1;jmaxn;j)f[i][j](c[i][j]f[i][j-1])%P;LL n,k;while(T--){scanf(%lld%lld,n,k);printf(%lld\n,F(n,k));}return 0;
} 转载于:https://www.cnblogs.com/asuldb/p/10206227.html
