BZOJ 1951 浅谈猪王国古代文字及中国剩余定理合并半拓展LuCas( 二 ) _lucas

那么求组合数时的mod数就是这个phi了
问题在于是一个质数，那他的phi就是，恰恰是一个合数，对合数求组合数，这不是拓展Lucas吗？

文章插图
考虑这个，作为题目给出的mod数却不是1e9+7之类的司空见惯的数，有点怪
【BZOJ 1951 浅谈猪王国古代文字及中国剩余定理合并半拓展LuCas】-1得到
这个东西质因数一分解，就是 2,3,4679,35617，全是质数，对于每一个质数可以使用Lucas，算出来5个值再用中国剩余定理合起来就好啦
然而我一开始先是打表没有打出35617，调了好久才发现
之后又是Lucas的时候mod写成了而不是mi，orz
两个小时就这么过去了
完整代码：

#include#includeusing namespace std;typedef long long dnt ;const dnt mod=999911659;dnt n,G;dnt saber[5][100050],inv[5][100050],m[5]={0,2,3,4679,35617};void init(dnt m,int typ){saber[typ][0]=inv[typ][0]=inv[typ][1]=1;for(int i=1;i<=m;i++) saber[typ][i]=saber[typ][i-1]*i%m;for(int i=2;i<=m;i++) inv[typ][i]=(m-m/i)*inv[typ][m%i]%m;for(int i=1;i<=m;i++) inv[typ][i]=inv[typ][i-1]*inv[typ][i]%m;}void exgcd(dnt a,dnt b,dnt &x,dnt &y){if(b==0){x=1,y=0;return ;}dnt x0,y0;exgcd(b,a%b,x0,y0);x=y0,y=x0-a/b*y0;}dnt inverse(dnt a,dnt m){dnt x,y;exgcd(a,m,x,y);return (x%m+m)%m;}dnt Misaka(dnt a,dnt b,dnt m,int typ){if(a>=1;}return rt;}int main(){for(int i=1;i<=4;i++)init(m[i],i);scanf("%lld%lld",&n,&G);dnt idx=cal();printf("%lld\n",quickmub(G,idx+mod-1));return 0;}/*EL PSY CONGROO*/

嗯，就是这样