2020-2021:teams:legal_string:jxm2001:万能欧几里得算法
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:万能欧几里得算法 [2021/08/20 18:59] jxm2001 |
2020-2021:teams:legal_string:jxm2001:万能欧几里得算法 [2021/08/22 15:16] (当前版本) jxm2001 [例题二] |
||
|---|---|---|---|
| 行 252: | 行 252: | ||
| } | } | ||
| return 0; | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | <hidden 卡常版> | ||
| + | <code cpp> | ||
| + | int C[MAXK][MAXK]; | ||
| + | struct Node{ | ||
| + | int cntr,cntu,f[MAXK][MAXK]; | ||
| + | Node(int cntr=0,int cntu=0){ | ||
| + | this->cntr=cntr; | ||
| + | this->cntu=cntu; | ||
| + | mem(f,0); | ||
| + | } | ||
| + | Node operator * (const Node &b)const{ | ||
| + | static int px[MAXK],py[MAXK]; | ||
| + | static int b1[MAXK][MAXK],b2[MAXK][MAXK]; | ||
| + | Node c; | ||
| + | int dx=cntr,dy=cntu; | ||
| + | px[0]=py[0]=1; | ||
| + | _for(i,1,MAXK) | ||
| + | px[i]=1LL*px[i-1]*dx%mod; | ||
| + | _for(i,1,MAXK) | ||
| + | py[i]=1LL*py[i-1]*dy%mod; | ||
| + | _for(i,0,MAXK)_rep(j,0,i){ | ||
| + | b1[i][j]=1LL*C[i][j]*px[i-j]%mod; | ||
| + | b2[i][j]=1LL*C[i][j]*py[i-j]%mod; | ||
| + | } | ||
| + | c.cntr=(cntr+b.cntr)%mod; | ||
| + | c.cntu=(cntu+b.cntu)%mod; | ||
| + | _for(i,0,MAXK)_for(j,0,MAXK){ | ||
| + | c.f[i][j]=f[i][j]; | ||
| + | _rep(i2,0,i)_rep(j2,0,j) | ||
| + | c.f[i][j]=(c.f[i][j]+1LL*b.f[i2][j2]*b1[i][i2]%mod*b2[j][j2])%mod; | ||
| + | } | ||
| + | return c; | ||
| + | } | ||
| + | }; | ||
| + | Node quick_pow(Node n,int k){ | ||
| + | Node ans=Node(0,0); | ||
| + | while(k){ | ||
| + | if(k&1)ans=ans*n; | ||
| + | k>>=1; | ||
| + | if(k)n=n*n; | ||
| + | } | ||
| + | return ans; | ||
| } | } | ||
| </code> | </code> | ||
2020-2021/teams/legal_string/jxm2001/万能欧几里得算法.1629457161.txt.gz · 最后更改: 2021/08/20 18:59 由 jxm2001
