点击查看代码
{
// Place your 全局 snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and
// description. Add comma separated ids of the languages where the snippet is applicable in the scope field. If scope
// is left empty or omitted, the snippet gets applied to all languages. The prefix is what is
// used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders.
// Placeholders with the same ids are connected.
// Example:
// "Print to console": {
// "scope": "javascript,typescript",
// "prefix": "log",
// "body": [
// "console.log('$1');",
// "$2"
// ],
// "description": "Log output to console"
// }
"basic" : {
"prefix" : "basic",
"body" : [
"/* Code by pp_orange */",
"//#pragma GCC optimize(2)",
"#include<bits/stdc++.h>",
"#define m_p(a,b) make_pair(a,b)",
"#define pb push_back",
"#define ll long long",
"#define ull unsigned long long",
"#define ld long double",
"#define inf 0x7FFFFFFF",
"#define inff 9223372036854775807",
"#define rep(i,l,r) for(int i=l;i<r;++i)",
"#define repp(i,l,r) for(int i=l;i<=r;++i)",
"#define per(i,r,l) for(int i=r-1;i>=l;--i)",
"#define pper(i,r,l) for(int i=r;i>=l;--i)",
"#define pii pair<int,int>",
"#define fi first",
"#define se second",
"#define p_q priority_queue",
"#define all(x) x.begin(),x.end()",
"#define rall(x) x.rbegin(),x.rend()",
"#define ls(x) ((x)<<1)",
"#define rs(x) ((x)<<1|1)",
"#define lb(x) ((x)&-(x))",
"#define lg(x) (31^__builtin_clz(x))",
"#define vi vector<int>",
"#define vii vector<pii >",
"const int mod = 998244353;",
"//#define int ll",
"const int intsz = sizeof(int);",
"using namespace std;",
"inline int rd(){",
"\tint x(0),f(1);char ch=getchar();",
"\twhile(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}",
"\twhile (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}",
"\treturn x*f;",
"}",
"inline void out(int X){",
"\tif(X<0) {X=~(X-1); putchar('-');}",
"\tif(X>9) out(X/10);",
"\tputchar(X%10+'0');",
"}",
"ll pw(ll x,int d){",
"\tll t = 1;",
"\tfor(;d;d>>=1,x=x*x%mod)if(d&1)t = t*x%mod;",
"\treturn t;",
"}",
"#define MAX 200005",
"signed main(){",
"\t//freopen(\"in.in\",\"r\",stdin);",
"\t//freopen(\"out.out\",\"w\",stdout);",
"\treturn 0;",
"}"
]
},
"myPoly" : {
"prefix" : "myPoly",
"body" : [
"namespace poly{",
" #define CTZ __builtin_ctz",
" const int de = 1;",
" const int G = 3;",
" const int Gi = pw(G,mod-2);",
" typedef complex<ld> cplx;",
" const ld pi = acos(-1);",
" int getN(int n){",
" int N = 1;",
" while(N<=n)N<<=1;",
" return N;",
" }",
" namespace polyTrs{",
" int r[MAX];",
" int nwsz = -1;",
" ",
" void initR(int N,int lim){",
" if(nwsz==lim)return ;",
" nwsz = lim;",
" rep(i,1,N)r[i] = (r[i>>1]>>1)|((i&1)<<(lim-1));",
" return ;",
" }",
" ",
" void NTT(int *a,int N,int tp){",
" //1:G, -1:Gi",
" //need init R",
" int x,y;",
" if(de)assert(CTZ(N)==nwsz);",
" const int g = tp==1?G:Gi;",
" int omg;",
" ll w;",
" rep(i,0,N)if(r[i]<i)swap(a[i],a[r[i]]);",
" for(int mid=1;mid<N;(mid<<=1)){",
" omg = pw(g,(mod-1)/(mid<<1));",
" for(int i=0,len=(mid<<1);i<N;i+=len){",
" w = 1;",
" for(int j=i;j<i+mid;++j,w=w*omg%mod){",
" x = a[j];",
" y = a[j+mid]*w%mod;",
" a[j] = (x+y)%mod;",
" a[j+mid] = (x-y+mod)%mod;",
" }",
" }",
" }",
" return ;",
" }",
" void FFT(cplx *a,int N,int tp){",
" //1:G, -1:Gi",
" //need init R",
" if(de)assert(CTZ(N)==nwsz);",
" int len;",
" cplx w,omg,x,y;",
" rep(i,0,N)if(r[i]<i)swap(a[r[i]],a[i]);",
" for(int mid=1;mid<N;mid<<=1){",
" len = mid<<1;",
" omg = {cos(pi/mid),tp*sin(pi/mid)};",
" for(int i=0;i<N;i+=len){",
" w = 1;",
" rep(j,i,i+mid){",
" x = a[j];",
" y = a[j+mid]*w;",
" a[j] = x+y;",
" a[j+mid] = x-y;",
" w *= omg;",
" }",
" }",
" }",
" return ;",
" }",
" }using polyTrs::NTT,polyTrs::initR,polyTrs::FFT;",
" ",
" namespace polyMul{",
" int tmp[MAX];",
" void Mul(int *a,int n,int *b,int m){",
" //Mul(rlt,n,b,m) , won't destroy b",
" //a^n and b^m",
" memcpy(tmp,b,intsz*(m+1));",
" int lim = 0;",
" int N = 1;",
" while(N<=n+m){",
" N <<= 1;",
" lim++;",
" }",
" initR(N,lim);",
" NTT(a,N,1);",
" NTT(b,N,1);",
" ll Ni = pw(N,mod-2);",
" rep(i,0,N)a[i] = (ll)a[i]*b[i]%mod*Ni%mod;",
" NTT(a,N,-1);",
" memcpy(b,tmp,intsz*(m+1));",
" //rep(i,0,N)cout<<tmp[i]<<',';cout<<endl;",
" memset(b+m+1,0,intsz*(N-(m+1)));",
" return ;",
" }",
" }using polyMul::Mul;",
" ",
" ",
" void Inv(int *b,int *a,int n){",
" //Inv(output,input,n) mod x^n , won't destroy a",
" //safe for *b",
" static int f[MAX];",
" if(de)assert(a[0]!=0);",
" int N = 1;",
" int lim = 0;",
" b[0] = pw(a[0],mod-2);b[1] = 0;",
" while(N<n){",
" lim++;",
" N <<= 1;",
" memset(b+N,0,intsz*N);",
" memcpy(f,a,intsz*N);",
" memset(f+N,0,intsz*N);",
" initR(N<<1,lim+1);",
" NTT(b,N*2,1);",
" NTT(f,N*2,1);",
" rep(i,0,N*2)f[i] = b[i]*(2-(ll)b[i]*f[i]%mod+mod)%mod;",
" NTT(f,N*2,-1);",
" ll Ni = pw(N*2,mod-2);",
" rep(i,0,N)b[i] = f[i]*Ni%mod;",
" memset(b+N,0,intsz*N);",
" }",
" memset(b+n,0,intsz*(N-n));",
" }",
" void Sqrt(int *b,int *a,int n){",
" //Sqrt(output,input,n) , mod x^n",
" static int gi[MAX];",
" static int f[MAX];",
" static const int inv2 = pw(2,mod-2);",
" int N = 1;",
" int lim = 0;",
" if(de)assert(a[0]==1);",
" b[0] = 1;b[1] = 0;",
" while(N<n){",
" lim++;",
" N <<= 1;",
" memset(b+N,0,intsz*N);",
" Inv(gi,b,N);",
" memset(gi+N,0,intsz*N);",
" memcpy(f,a,intsz*N);",
" memset(f+N,0,intsz*N);",
" initR(N*2,lim+1);",
" NTT(gi,N*2,1);",
" NTT(f,N*2,1);",
" NTT(b,N*2,1);",
" ll Ni = pw(N*2,mod-2);",
" rep(i,0,N*2)b[i] = ((ll)f[i]*gi[i]%mod+b[i])*inv2%mod*Ni%mod;",
" NTT(b,N*2,-1);",
" memset(b+N,0,intsz*N);",
" }",
" memset(b+n,0,intsz*(N-n));",
" return ;",
" }",
" ",
" void Dev(int *a,int n){",
" //get Dev [ 0 , n )",
" rep(i,0,n-1)a[i] = ((ll)a[i+1]*(i+1))%mod;",
" a[n-1] = 0;",
" return ;",
" }",
" ",
" namespace polyInter{",
" int inv[MAX] = {0,1};",
" int invsz = 1;",
" void initInv(int sz){",
" if(sz<=invsz)return ;",
" repp(i,2,sz)inv[i] = (mod-(ll)inv[mod%i]*(mod/i)%mod);",
" invsz = sz;",
" }",
" void Inter(int *a,int n){",
" //get Inter [ 0 , n )",
" initInv(n);",
" per(i,n,1)a[i] = ((ll)a[i-1]*inv[i])%mod;",
" a[0] = 0;",
" return ;",
" }",
" }using polyInter::Inter;",
" ",
" void Ln(int *b,int *a,int n){",
" //Ln(out,in,n) , won't destroy a , mod x^n",
" static int tmp[MAX];",
" memcpy(tmp,a,intsz*n);",
" int N = getN(n-1)*2;",
" if(de)assert(a[0]==1);",
" memcpy(b,a,intsz*N);",
" Inv(a,b,n);",
" Dev(b,n);",
" ",
" initR(N,CTZ(N));",
" NTT(a,N,1);",
" NTT(b,N,1);",
" ll Ni = pw(N,mod-2);",
" rep(i,0,N)b[i] = ((ll)a[i]*b[i]%mod*Ni)%mod;",
" NTT(b,N,-1);",
" memset(b+n,0,intsz*(N-n));",
" Inter(b,n);",
" memcpy(a,tmp,intsz*n);",
" memset(a+n,0,intsz*(N-n));",
" return ;",
" }",
" ",
" void Exp(int *b,int *a,int n){",
" //Exp(out,in,n) , won't destroy a",
" // mod x^n",
" static int c[MAX],d[MAX];",
" if(de)assert(a[0]==0);",
" int N = 1,lim = 0;",
" b[0] = 1,b[1] = 0;",
" while(N<n){",
" N <<= 1;",
" lim++;",
" memset(b+N,0,intsz*N);",
" Ln(c,b,N);",
" memcpy(d,a,intsz*N);",
" memset(d+N,0,intsz*N);",
" initR(N*2,lim+1);",
" NTT(b,N*2,1);",
" NTT(c,N*2,1);",
" NTT(d,N*2,1);",
" ll Ni = pw(N*2,mod-2);",
" rep(i,0,N*2)b[i] = (1ll-c[i]+d[i]+mod)%mod*b[i]%mod*Ni%mod;",
" NTT(b,N*2,-1);",
" memset(b+N,0,intsz*N);",
" }",
" memset(b+n,0,intsz*(N-n));",
" return ;",
" }",
" void MTT(int *a,int n,int *b,int m,const int p){",
" static const int B = 1<<15;",
" static cplx f[MAX],g1[MAX],g2[MAX];",
" static const int cplxsz = sizeof(cplx);",
" int N = getN(n+m);",
" memset(f,0,cplxsz*N);",
" memset(g1,0,cplxsz*N);",
" memset(g2,0,cplxsz*N);",
" initR(N,CTZ(N));",
" repp(i,0,n)f[i] = {a[i]%B,a[i]/B};",
" FFT(f,N,1);",
" repp(i,0,m)g1[i] = b[i]%B;",
" FFT(g1,N,1);",
" repp(i,0,m)g2[i] = b[i]/B;",
" FFT(g2,N,1);",
" rep(i,0,N)g1[i] *= f[i]/(ld)N,g2[i] *= f[i]/(ld)N;",
" FFT(g1,N,-1);",
" FFT(g2,N,-1);",
" repp(i,0,n+m)",
" a[i] = (((ll)(g1[i].real()+0.5)%p)",
" +((ll)(g1[i].imag()+0.5)+(ll)(g2[i].real()+0.5))%p*B%p",
" +((ll)(g2[i].imag()+0.5))%p*B%p*B%p)%p;",
" return ;",
" }",
"}",
}
]
},
"myExpoly" : {
"prefix" : "myExpoly",
"body" : [
"\tnamespace polyPow{",
"\t//暂不支持多测",
"\t\tint tmp[MAX];",
"\t\tint c[MAX];",
"\t\tvoid Pow(int *b,int *a,int n,ll d){",
"\t\t\tif(d==0){",
"\t\t\t\tmemset(b,0,intsz*n);",
"\t\t\t\tb[0] = 1;",
"\t\t\t\treturn ;",
"\t\t\t}",
"\t\t//Pow(rlt&input,len,times); mod x^len",
"\t\t\tif(de)assert(a[0]==1);",
"\t\t\tLn(tmp,a,n);",
"\t\t\trep(i,0,n)tmp[i] = (tmp[i]*d)%mod;",
"\t\t\tExp(b,tmp,n);",
"\t\t\treturn ;",
"\t\t}",
"\t\tvoid exPow(int *b,int *a,int n,ll d,ll d2 = -1){",
"\t\t//exPow(rlt&input,len,times%mod,times%(mod-1)); mod x^len",
"\t\t\tif(d2==-1)d2=d;",
"\t\t\tif(d==0){",
"\t\t\t\tmemset(b,0,intsz*n);",
"\t\t\t\tb[0] = pw(a[0],d2);",
"\t\t\t\treturn ;",
"\t\t\t}",
"\t\t\tint cnt = 0;",
"\t\t\trep(i,0,n){",
"\t\t\t\tif(a[i]==0)cnt++;",
"\t\t\t\telse break;",
"\t\t\t}",
"\t\t\tll m = cnt*d;",
"\t\t\tif(m>=n){",
"\t\t\t\tmemset(b,0,intsz*n);",
"\t\t\t\treturn ;",
"\t\t\t}",
"\t\t\tll f0 = a[cnt];",
"\t\t\tll if0 = pw(f0,mod-2);",
"\t\t\tmemcpy(c,a+cnt,intsz*(n-m));",
"\t\t\trep(i,0,n-m)c[i] = (c[i]*if0)%mod;",
"\t\t\tPow(b+m,c,n-m,d);",
"\t\t\tmemset(b,0,intsz*m);",
"\t\t\tf0 = pw(f0,d2);",
"\t\t\trep(i,m,n)b[i] = (b[i]*f0)%mod;",
"\t\t\treturn ;",
"\t\t}",
"\t}using polyPow::Pow,polyPow::exPow;",
"\tvoid Rev(int *a,int n){",
"\t\treverse(a,a+n+1);",
"\t\treturn ;",
"\t}",
"\tnamespace polyDiv{",
"\t\tint gi[MAX];",
"\t\tint tmpg[MAX];",
"\t\tvoid Div(int *q,int *r,int *f,int n,int *g,int m){",
"\t\t//f(n) = q(n-m)*g(m)+r(m-1)",
"\t\t// memset(gi,0,sizeof(gi));",
"\t\t\tmemset(tmpg,0,intsz*getN(n));",
"\t\t\tassert(m<=n);",
"\t\t\tRev(f,n);Rev(g,m);",
"\t\t\tint sz = n-m+1;",
"\t\t\tmemcpy(tmpg,g,intsz*sz);",
"\t\t\tInv(gi,tmpg,sz);",
"\t\t\tMul(gi,sz-1,f,n);",
"\t\t\tmemcpy(q,gi,intsz*sz);",
"\t\t\tRev(f,n);Rev(g,m);Rev(q,n-m);",
"\t\t\t//memset(q)...",
"\t\t\tmemcpy(tmpg,q,intsz*sz);",
"\t\t\tMul(tmpg,n-m,g,m);",
"\t\t\trep(i,0,m)r[i] = (f[i]-tmpg[i]+mod)%mod;",
"\t\t\treturn ;",
"\t\t}",
"\t}using polyDiv::Div;",
"\tnamespace polyMod{",
"\t\tint tmp[MAX];",
"\t\tvoid Mod(int *r,int *f,int n,int *g,int m){",
"\t\t// memset(tmp,0,sizeof(tmp));",
"\t\t\tDiv(tmp,r,f,n,g,m);",
"\t\t\treturn ;",
"\t\t}",
"\t}using polyMod::Mod;",
"\tnamespace polyBM{",
"\t//暂不支持多测",
"\t\tint v[MAX];",
"\t\tint tmp[MAX];",
"\t\tvoid BM(int *r,int *f,int k,int d){",
"\t\t\tr[0] = 1;",
"\t\t\tint N = getN((k-1)*2);",
"\t\t\tint lim = CTZ(N);",
"\t\t\tll Ni = pw(N,mod-2);",
"\t\t\tv[1] = 1;",
"\t\t\tinitR(N,lim);",
"\t\t\tfor(;d;d>>=1){",
"\t\t\t\tif(d&1){",
"\t\t\t\t\tmemcpy(tmp,r,intsz*N);",
"\t\t\t\t\tMul(tmp,k-1,v,k-1);",
"\t\t\t\t\tMod(r,tmp,N-1,f,k);",
"\t\t\t\t}",
"\t\t\t\tif(d==1)return;",
"\t\t\t\tmemcpy(tmp,v,intsz*N);",
"\t\t\t\tinitR(N,lim);",
"\t\t\t\tNTT(tmp,N,1);",
"\t\t\t\trep(i,0,N)tmp[i] = ((ll)tmp[i]*tmp[i]%mod*Ni)%mod;",
"\t\t\t\tNTT(tmp,N,-1);",
"\t\t\t\tMod(v,tmp,N,f,k);",
"\t\t\t}",
"\t\t\treturn ;",
"\t\t}",
"\t}using polyBM::BM;",
"\tnamespace polyMSB{",
"\t// 不支持多测自动清空",
"\t// MSB(F(x),Q(x),Q.len,power)",
"\t// return [x^d] F(x)/Q(x) ",
"\t\tint tmpf[MAX],tmpq[MAX];",
"\t\tint qq[MAX],ff[MAX];",
"\t\tint qi[MAX];",
"\t\tint MSB(int *f,int *q,int n,int d){",
"\t\t\tint N = getN(n);",
"\t\t\tint NN = N<<1;",
"\t\t\tll w = pw(G,(mod-1)/NN),omg;",
"\t\t\tll wi = pw(w,mod-2);",
"\t\t\tll Ni = pw(N,mod-2), inv2 = pw(2,mod-2);",
"\t\t\tmemcpy(tmpf,f,NN);",
"\t\t\tmemcpy(tmpq,q,NN);",
"\t\t\tinitR(N,CTZ(N));",
"\t\t\tNTT(f,N,1);",
"\t\t\tNTT(q,N,1);",
"\t\t\twhile(d>=N){",
"\t\t\t\tmemcpy(ff,f,intsz*N);",
"\t\t\t\tmemcpy(qq,q,intsz*N);",
"\t\t\t\tNTT(ff,N,-1);NTT(qq,N,-1);",
"\t\t\t\tomg = 1;",
"\t\t\t\trep(i,0,N){",
"\t\t\t\t\tff[i] = ff[i]*omg%mod*Ni%mod;",
"\t\t\t\t\tqq[i] = qq[i]*omg%mod*Ni%mod;",
"\t\t\t\t\tomg = (omg*w)%mod;",
"\t\t\t\t}",
"\t\t\t\tNTT(ff,N,1);NTT(qq,N,1);",
"\t\t\t\tper(i,N,0)ff[(i<<1)|1] = ff[i];",
"\t\t\t\tper(i,N,0)qq[(i<<1)|1] = qq[i];",
"\t\t\t\tper(i,N,0)ff[i<<1] = f[i];",
"\t\t\t\tper(i,N,0)qq[i<<1] = q[i];",
"\t\t\t\trep(i,0,N)q[i] = ((ll)qq[i]*qq[i+N])%mod;",
"\t\t\t\tif(d&1){",
"\t\t\t\t\tomg = 1;",
"\t\t\t\t\trep(i,0,N){",
"\t\t\t\t\t\tf[i] = ((ll)ff[i]*qq[i+N]-(ll)ff[i+N]*qq[i]%mod+mod)%mod*omg%mod*inv2%mod;",
"\t\t\t\t\t\tomg = (omg*wi)%mod;",
"\t\t\t\t\t}",
"\t\t\t\t}else{",
"\t\t\t\t\trep(i,0,N){",
"\t\t\t\t\t\tf[i] = ((ll)ff[i]*qq[i+N]+(ll)ff[i+N]*qq[i])%mod*inv2%mod;",
"\t\t\t\t\t}",
"\t\t\t\t}",
"\t\t\t\td >>= 1;",
"\t\t\t}",
"\t\t\tNTT(f,N,-1);NTT(q,N,-1);",
"\t\t\tInv(qi,q,N);",
"\t\t\tll rlt = 0;",
"\t\t\trepp(i,0,d)rlt = (rlt + (ll)f[i]*qi[d-i])%mod;",
"\t\t\tmemcpy(f,tmpf,NN);",
"\t\t\tmemcpy(q,tmpq,NN);",
"\t\t\treturn rlt;",
"\t\t}",
"\t}using polyMSB::MSB;",
"\tnamespace polyLSB{",
"\t// 不支持多测自动清空",
"\t// LSB(F(x),Q(x),Q.len,power)",
"\t// return [x^d] F(x)/Q(x) ",
"\t// 等价于MSB,简要实现,常数略慢于MSB",
"\t\tint F[MAX],Q[MAX];",
"\t\tint tmpf[MAX],tmpq[MAX];",
"\t\tint LSB(int *f,int *q,int n,int d){",
"\t\t\tint N = getN(n*2);",
"\t\t\tint Mid = N/2;",
"\t\t\tll Ni = pw(N,mod-2);",
"\t\t\tmemcpy(tmpf,f,intsz*N);",
"\t\t\tmemcpy(tmpq,q,intsz*N);",
"\t\t\tinitR(N,CTZ(N));",
"\t\t\twhile(d){",
"\t\t\t\tNTT(f,N,1);NTT(q,N,1);",
"\t\t\t\trep(i,0,N)F[i] = (ll)f[i]*q[i^Mid]%mod*Ni%mod;",
"\t\t\t\trep(i,0,N)Q[i] = (ll)q[i]*q[i^Mid]%mod*Ni%mod;",
"\t\t\t\tNTT(F,N,-1);NTT(Q,N,-1);",
"\t\t\t\tbool flag = d&1;",
"\t\t\t\trep(i,0,Mid)f[i] = F[i<<1|flag];",
"\t\t\t\trep(i,0,Mid)q[i] = Q[i<<1];",
"\t\t\t\tmemset(f+Mid,0,intsz*Mid);",
"\t\t\t\tmemset(q+Mid,0,intsz*Mid);",
"\t\t\t\td >>= 1;",
"\t\t\t}",
"\t\t\tint rlt = (ll)f[0]*pw(q[0],mod-2)%mod;",
"\t\t\tmemcpy(f,tmpf,intsz*N);",
"\t\t\tmemcpy(q,tmpq,intsz*N);",
"\t\t\treturn rlt;",
"\t\t}",
"\t}using polyLSB::LSB;",
" void ChirpZ(int *a,int *b,int n,const int c){",
" // 需要保证 b 是干净的",
" static int c1[MAX],c2[MAX];",
" const int invc = pw(c,mod-2);",
" c1[0] = c1[1] = 1;",
" repp(i,2,n*2-2)c1[i] = (ll)c1[i-1]*c%mod;",
" repp(i,3,n*2-2)c1[i] = (ll)c1[i-1]*c1[i]%mod;",
" c2[0] = c2[1] = 1;",
" repp(i,2,n)c2[i] = (ll)c2[i-1]*invc%mod;",
" repp(i,3,n)c2[i] = (ll)c2[i-1]*c2[i]%mod;",
" rep(i,0,n)b[n-i-1] = ((ll)a[i]*c2[i])%mod;",
" poly::Mul(b,n-1,c1,n*2-2);",
" rep(i,0,n)b[i] = (ll)b[i+n-1]*c2[i]%mod;",
" memset(b+n,0,intsz*n*3);",
" return ;",
" }",
" void Exsqrt(int *b,int *a,int n){",
" // 在模x^n意义下对a开根, 存入b中, 对于二次剩余保留较小的根",
" // 需要提前导入数论库.",
" ll k = num_theory::Sqrt(a[0],mod);",
" ll i0 = pw(a[0],mod-2);",
" ll yy = a[0];",
" rep(i,0,n)a[i] = (a[i]*i0)%mod;",
" Sqrt(b,a,n);",
" rep(i,0,n)a[i] = (a[i]*yy)%mod;",
" rep(i,0,n)b[i] = (b[i]*k)%mod;",
" return ;",
"}",
]
}
"myMath" : {
"prefix" : "myMath",
"body" : [
"ll fac[MAX],ifac[MAX],idig[MAX];",
"void initComb(){",
" fac[0] = 1;",
" rep(i,1,MAX)fac[i] = (fac[i-1]*i)%mod;",
" ifac[MAX-1] = pw(fac[MAX-1],mod-2);",
" pper(i,MAX-2,0)ifac[i] = (ifac[i+1]*(i+1))%mod;",
" rep(i,1,MAX)idig[i] = ifac[i]*fac[i-1]%mod;",
" return ;",
"}",
"ll Comb(int x,int y){//choose y from x itms",
" if(x<0||y<0||y>x)return 0;",
" return fac[x]*ifac[y]%mod*ifac[x-y]%mod;",
"}"
]
},
"myModMath" : {
"prefix" : "myModMath",
"body" : [
"mint fac[MAX],ifac[MAX],idig[MAX];",
"void initComb(){",
" fac[0] = mint(1);",
" rep(i,1,MAX)fac[i] = fac[i-1]*i;",
" ifac[MAX-1] = fac[MAX-1].inv();",
" pper(i,MAX-2,0)ifac[i] = ifac[i+1]*(i+1);",
" rep(i,1,MAX)idig[i] = ifac[i]*fac[i-1];",
" return ;",
"}",
"mint Comb(int x,int y){//choose y from x itms",
" if(x<0||y<0||y>x)return 0;",
" return fac[x]*ifac[y]*ifac[x-y];",
"}"
]
},
"myDinic" : {
"prefix" : "myDinic",
"body" : [
"namespace Dinic{",
" const int N = 205;",
" const int M = 10005;",
" int fir[N];",
" int cur[N];",
" int e[M],flw[M],nxt[M];",
" int dis[N];",
" int flowS,flowT;",
" int tot = 1;",
" queue<int> q;",
" void adde(int x,int y,int z){",
" nxt[++tot] = fir[x];",
" fir[x] = tot;",
" flw[tot] = z;",
" e[tot] = y;",
" nxt[++tot] = fir[y];",
" fir[y] = tot;",
" flw[tot] = 0;",
" e[tot] = x;",
" return ;",
" }",
" bool bfs(){",
" memset(dis,0x3f,sizeof(dis));",
" memcpy(cur,fir,sizeof(fir));",
" while(!q.empty())q.pop();",
" q.push(flowS);",
" dis[flowS] = 0;",
" while(!q.empty()){",
" int x = q.front();q.pop();",
" // cout<<fir[x]<<',';",
" if(x==flowT)return 1;",
" for(int i=fir[x],y;i;i=nxt[i]){",
" y = e[i];",
" if(flw[i]){",
" if(dis[y]>dis[x]+1){",
" dis[y] = dis[x]+1;",
" q.push(y);",
" }",
" }",
" }",
" }",
" return 0;",
" }",
" ll dfs(int x,ll infl){",
" if(!infl)return 0;",
" if(x==flowT)return infl;",
" ll res = infl,tmp;",
" for(int i=cur[x],y;i&&res;i=nxt[i]){",
" cur[x] = i;",
" y = e[i];",
" if(dis[y]!=dis[x]+1)continue;",
" tmp = dfs(y,min(res,(ll)flw[i]));",
" flw[i] -= tmp;",
" flw[i^1] += tmp;",
" res -= tmp;",
" }",
" return infl-res;",
" }",
" ll dinic(){",
" ll rlt = 0;",
" while(bfs()){",
" rlt += dfs(flowS,inff);",
" }",
" return rlt;",
" }",
"}",
"using Dinic::dinic,Dinic::adde,Dinic::flowS,Dinic::flowT;"
]
},
"myMCMF" : {
"prefix" : "myMCMF" ,
"body" : [
"namespace MCMF{",
" const int N = 1005;",
" const int M = 200005;",
" int fir[N];",
" int e[M],flw[M],nxt[M],cost[M];",
" int dis[N];",
" int pa[N],pre[N];",
" bool in[N];",
" int flowS=-1,flowT=-1;",
" int tot = 1;",
" int vernum = 0;",
" queue<int> q;",
" void clear(){",
" flowS = -1,flowT = -1;",
" memset(fir,0,intsz*(vernum+2));",
" tot = 1;",
" vernum = 0;",
" return ;",
" }",
" void adde(int x,int y,int z,int w){",
" // add x->y flow=z, cost=w",
" vernum = max(vernum,max(x,y));",
" nxt[++tot] = fir[x];",
" fir[x] = tot;",
" flw[tot] = z;",
" e[tot] = y;",
" cost[tot] = w;",
" nxt[++tot] = fir[y];",
" fir[y] = tot;",
" flw[tot] = 0;",
" e[tot] = x;",
" cost[tot] = -w;",
" return ;",
" }",
" bool SPFA(){",
" while(!q.empty())q.pop();",
" memset(dis,0x3f,sizeof(dis));",
" dis[flowS] = 0;",
" q.push(flowS);",
" while(!q.empty()){",
" int x = q.front();q.pop();",
" in[x] = 0;",
" for(int i=fir[x],y;i;i=nxt[i]){",
" y = e[i];",
" if(flw[i]&&dis[y]>dis[x]+cost[i]){",
" pa[y] = x;",
" pre[y] = i;",
" dis[y] = dis[x]+cost[i];",
" if(!in[y]){",
" in[y] = 1;",
" q.push(y);",
" }",
" }",
" }",
" }",
" return dis[flowT]<100000000;",
" }",
" pii getpath(){",
" int nw = flowT;",
" int fl=inf,co=0;",
" while(nw!=flowS)fl = min(fl,flw[pre[nw]]),co+=cost[pre[nw]],nw=pa[nw];",
" co *= fl;",
" // cout<<fl<<endl;",
" nw = flowT;",
" while(nw!=flowS){",
" flw[pre[nw]] -= fl;",
" flw[pre[nw]^1] += fl;",
" nw = pa[nw];",
" }",
" return m_p(fl,co);",
" }",
" const pii operator + (const pii &x,const pii &y){return m_p(x.fi+y.fi,x.se+y.se);}",
" const void operator += (pii &x,const pii &y){x = x+y;return ;}",
" pii mcmf(){",
" // (flow,cost)",
" assert(flowS!=-1&&flowT!=-1);",
" pii rlt = {0,0};",
" while(SPFA())rlt += getpath();",
" return rlt;",
" }",
"}",
"using MCMF::mcmf,MCMF::adde,MCMF::flowS,MCMF::flowT;",
]
},
"myCplx" : {
"prefix" : "myCplx",
"body" : [
"struct Cplx{",
" ld a,b;",
" Cplx(){a = 0 , b = 0;}",
" Cplx(ld real,ld image){a = real,b = image;}",
" Cplx(ld thta){a = cos(thta), b = sin(thta);}",
"};",
"const Cplx operator + (const Cplx x,const Cplx y){return Cplx(x.a+y.a,x.b+y.b);}",
"const void operator += (Cplx &x,const Cplx y){x = x+y;}",
"const Cplx operator - (const Cplx x,const Cplx y){return Cplx(x.a-y.a,x.b-y.b);}",
"const void operator -= (Cplx &x,const Cplx y){x = x-y;}",
"const Cplx operator * (const Cplx x,const Cplx y){return Cplx(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}",
"const void operator *= (Cplx &x,const Cplx y){x = x*y;}",
"ostream& operator << (ostream &cout,const Cplx x){cout<<'('<<x.a<<','<<x.b<<')';return cout;}"
]
},
"myExpair" : {
"prefix" : "myExpair",
"body" : [
"const pii operator + (const pii x,const pii y){return m_p(x.fi+y.fi,x.se+y.se);}",
"const void operator += (pii &x,const pii y){x = x+y;return ;}",
"const pii operator - (const pii x,const pii y){return m_p(x.fi-y.fi,x.se-y.se);}",
"const void operator -= (pii &x,const pii y){x = x-y;return ;}",
"const pii operator * (const pii x,const pii y){return m_p(x.fi*y.fi,x.se*y.se);}",
"const void operator *= (pii &x,const pii y){x = x*y;return ;}",
"ostream& operator << (ostream &cout,const pii x){cout<<'('<<x.fi<<','<<x.se<<')';return cout;}"
]
},
"myMatrix" : {
"prefix" : "myMatrix",
"body" : [
"const int M_sz = 2;",
"struct Matrix{",
" mint a[M_sz][M_sz];",
" Matrix(){",
" memset(a,0,sizeof(a));",
" return ;",
" }",
" Matrix(int tp){",
" memset(a,0,sizeof(a));",
" if(tp==1)rep(i,0,M_sz)a[i][i] = 1;",
" }",
" mint* operator [](int x){",
" return a[x];",
" }",
" void clear(){",
" memset(a,0,sizeof(a));",
" return ;",
" }",
" mint det(int n){",
" static mint b[M_sz][M_sz];",
" memcpy(b,a,sizeof(a));",
" mint rlt = 1;",
" int idx;",
" mint iv;",
" rep(i,0,n){",
" idx = -1;",
" rep(j,i,n){",
" if(b[j][i].v!=0){",
" idx = j;",
" break;",
" }",
" }",
" if(idx==-1)return 0;",
" if(idx!=i){",
" rlt *= -1;",
" swap(b[i],b[idx]);",
" }",
" rlt *= b[i][i];",
" iv = b[i][i].inv();",
" rep(j,i,n)b[i][j] *= iv;",
" rep(j,i+1,n){",
" if(b[j][i].v==0)continue;",
" rep(k,i+1,n)b[j][k] -= b[j][i]*b[i][k];",
" b[j][i] = 0;",
" }",
" }",
" return rlt;",
" }",
"};",
"const Matrix operator * (Matrix x,Matrix y){",
" Matrix c(0);",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" rep(k,0,M_sz){",
" c[i][j] = c[i][j]+x[i][k]*y[k][j];",
" }",
" }",
" }",
" return c;",
"}",
"void operator *= (Matrix &x,Matrix y){x = x*y;}",
"const Matrix operator + (Matrix x,Matrix y){",
" Matrix c(0);",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" c[i][j] = x[i][j]+y[i][j];",
" }",
" }",
" return c;",
"}",
"void operator += (Matrix &x,Matrix y){",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" x[i][j] = x[i][j]+y[i][j];",
" }",
" }",
"}",
"const Matrix operator - (Matrix x,Matrix y){",
" Matrix c(0);",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" c[i][j] = x[i][j]-y[i][j];",
" }",
" }",
" return c;",
"}",
"void operator -= (Matrix &x,Matrix y){",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" x[i][j] = x[i][j]-y[i][j];",
" }",
" }",
"}",
"ostream& operator << (ostream &cout,Matrix x){",
" rep(i,0,M_sz){",
" rep(j,0,M_sz){",
" cout<<x[i][j]<<' ';",
" }cout<<endl;",
" }",
" return cout;",
"}",
"Matrix pw(Matrix x,ll d){",
" Matrix t(1);",
" for(;d;d>>=1,x=x*x){",
" if(d&1)t*=x;",
" }",
" return t;",
"}",
]
},
"myModint" : {
"prefix" : "myModint",
"body" : [
"struct mint{",
" int v;",
" mint(){v = 0;}",
" mint(int x){v = x;if(v<0)v+=mod;}",
" mint inv(){return mint(pw(v,mod-2));}",
"};",
"mint& operator += (mint&x,const mint y){x.v+=y.v;if(x.v>=mod)x.v-=mod;return x;}",
"const mint operator + (const mint x,const mint y){int rlt=x.v+y.v;if(rlt>=mod)rlt-=mod;return rlt;}",
"mint& operator -= (mint&x,const mint y){x.v-=y.v;if(x.v<0)x.v+=mod;return x;}",
"const mint operator - (const mint x,const mint y){int rlt=x.v-y.v;if(rlt<0)rlt+=mod;return rlt;}",
"mint& operator *= (mint&x,const mint y){x.v=(ll)x.v*y.v%mod;return x;}",
"const mint operator * (const mint x,const mint y){return (ll)x.v*y.v%mod;}",
"mint& operator /= (mint&x,const mint y){x.v=(ll)x.v*pw(y.v,mod-2)%mod;return x;}",
"const mint operator / (const mint x,const mint y){return (ll)x.v*pw(y.v,mod-2)%mod;}",
"ostream & operator << (ostream & cout , mint x){cout<<x.v;return cout;}",
"mint pw(mint x,int d){",
" mint t = 1;",
" for(;d;d>>=1,x=x*x)if(d&1)t = t*x;",
" return t;",
"}",
]
},
"myLCA" : {
"prefix" : "myLCA",
"body" : [
"namespace myLCA{",
" int lg[MAX];",
" bool isinitlg = 0;",
" inline void initlg(){",
" if(!isinitlg){",
" isinitlg = 1;",
" rep(i,2,MAX)lg[i] = lg[i>>1]+1;",
" }",
" return ;",
" }",
" int dep[MAX];",
" int f[MAX][20];",
" void LCAdfs(int x,int fa){",
" dep[x] = dep[fa]+1;",
" f[x][0] = fa;",
" repp(j,1,lg[dep[x]])f[x][j] = f[f[x][j-1]][j-1];",
" for(auto to:v[x])if(to!=fa)LCAdfs(to,x);",
" return ;",
" }",
" inline void initLCA(int rt){",
" initlg();",
" LCAdfs(rt,0);",
" return ;",
" }",
" int LCA(int x,int y){",
" if(dep[x]>dep[y])swap(x,y);//x<y",
" while(dep[x]<dep[y])y = f[y][lg[dep[y]-dep[x]]];",
" if(x==y)return x;",
" per(i,lg[dep[x]]+1,0)if(f[x][i]!=f[y][i])x = f[x][i] , y = f[y][i];",
" return f[x][0];",
" }",
"}using myLCA::LCA,myLCA::initLCA;"
]
},
"myPrime" : {
"prefix" : "myPrime",
"body" : [
"int prm[MAX];",
"bool isp[MAX];",
"int pcnt = 0;",
"void initprm(){",
" rep(i,2,MAX)isp[i] = 1;",
" int x;",
" rep(i,2,MAX){",
" if(isp[i]){",
" prm[pcnt++] = i;",
" }",
" for(int j=0;j<pcnt&&(x=i*prm[j])<MAX;j++){",
" isp[x] = 0;",
" if(i%prm[j]==0){",
" break;",
" }",
" }",
" }",
" return ;",
"}"
]
},
"myTrain" : {
"prefix" : "myTrain",
"body" : [
"#pragma GCC optimize(3)",
"#pragma GCC target(\"avx\")",
"#pragma GCC optimize(\"Ofast\")",
"#pragma GCC optimize(\"inline\")",
"#pragma GCC optimize(\"-fgcse\")",
"#pragma GCC optimize(\"-fgcse-lm\")",
"#pragma GCC optimize(\"-fipa-sra\")",
"#pragma GCC optimize(\"-ftree-pre\")",
"#pragma GCC optimize(\"-ftree-vrp\")",
"#pragma GCC optimize(\"-fpeephole2\")",
"#pragma GCC optimize(\"-ffast-math\")",
"#pragma GCC optimize(\"-fsched-spec\")",
"#pragma GCC optimize(\"unroll-loops\")",
"#pragma GCC optimize(\"-falign-jumps\")",
"#pragma GCC optimize(\"-falign-loops\")",
"#pragma GCC optimize(\"-falign-labels\")",
"#pragma GCC optimize(\"-fdevirtualize\")",
"#pragma GCC optimize(\"-fcaller-saves\")",
"#pragma GCC optimize(\"-fcrossjumping\")",
"#pragma GCC optimize(\"-fthread-jumps\")",
"#pragma GCC optimize(\"-funroll-loops\")",
"#pragma GCC optimize(\"-fwhole-program\")",
"#pragma GCC optimize(\"-freorder-blocks\")",
"#pragma GCC optimize(\"-fschedule-insns\")",
"#pragma GCC optimize(\"inline-functions\")",
"#pragma GCC optimize(\"-ftree-tail-merge\")",
"#pragma GCC optimize(\"-fschedule-insns2\")",
"#pragma GCC optimize(\"-fstrict-aliasing\")",
"#pragma GCC optimize(\"-fstrict-overflow\")",
"#pragma GCC optimize(\"-falign-functions\")",
"#pragma GCC optimize(\"-fcse-skip-blocks\")",
"#pragma GCC optimize(\"-fcse-follow-jumps\")",
"#pragma GCC optimize(\"-fsched-interblock\")",
"#pragma GCC optimize(\"-fpartial-inlining\")",
"#pragma GCC optimize(\"no-stack-protector\")",
"#pragma GCC optimize(\"-freorder-functions\")",
"#pragma GCC optimize(\"-findirect-inlining\")",
"#pragma GCC optimize(\"-fhoist-adjacent-loads\")",
"#pragma GCC optimize(\"-frerun-cse-after-loop\")",
"#pragma GCC optimize(\"inline-small-functions\")",
"#pragma GCC optimize(\"-finline-small-functions\")",
"#pragma GCC optimize(\"-ftree-switch-conversion\")",
"#pragma GCC optimize(\"-foptimize-sibling-calls\")",
"#pragma GCC optimize(\"-fexpensive-optimizations\")",
"#pragma GCC optimize(\"-funsafe-loop-optimizations\")",
"#pragma GCC optimize(\"inline-functions-called-once\")",
"#pragma GCC optimize(\"-fdelete-null-pointer-checks\")",
]
},
"myIOfast" : {
"prefix" : "myOIfast",
"body" : [
"namespace FastIO {",
" const int SZ=(1<<21)+1;",
" struct I {",
" char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;",
" I(FILE*f):fi(f){}",
" inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}",
" inline ll operator()(){ll x;operator()(x);return x;}",
" inline I&operator()(char&x){x=Gc();return*this;}",
" inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\\n'&&c!='\\r';++s,c=Gc())*s=c;*s=0;return*this;}",
" template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}",
" template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}",
" } rd(stdin);",
" struct O {",
" char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;",
" O(FILE*f):fi(f){}",
" ~O(){Flush();}",
" inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}",
" inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}",
" inline O&operator()(char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}",
" inline O&operator()(const char*s){return operator()((char*)s);}",
" template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}",
" template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}",
" } out(stdout);",
"}",
"using namespace FastIO;",
]
},
"myVePoly" : {
"prefix" : "myVePoly",
"body" : [
"namespace vepoly{",
" int A[MAX],B[MAX];",
" vector<int> mul(vector<int> a,vector<int> b){",
" int al = (int)a.size()-1,bl = (int)b.size()-1;",
" int N = 1;",
" while(N<=al+bl)N <<= 1;",
" memset(A,0,intsz*N);memset(B,0,intsz*N);",
" repp(i,0,al)A[i] = a[i];",
" repp(i,0,bl)B[i] = b[i];",
" vector<int> c(al+bl+1,0);",
" poly::Mul(A,al,B,bl);",
" repp(i,0,al+bl)c[i] = A[i];",
" return c;",
" }",
" vector<int> add(vector<int> a,vector<int> b){",
" vector<int> c(max(a.size(),b.size()),0);",
" int mn = min(a.size(),b.size());",
" rep(i,0,mn)c[i] = (a[i]+b[i])%mod;",
" if(a.size()>b.size())rep(i,mn,c.size())c[i] = a[i];",
" else rep(i,mn,c.size())c[i] = b[i];",
" return c;",
" }",
"}using vepoly::mul,vepoly::add;",
]
},
"myNumTheory" : {
"prefix" : "myNumTheory",
"body" : [
"namespace num_theory{",
" typedef __int128 lll;",
" ostream& operator << (ostream &cout,lll x){",
" vector<int> v;",
" do{",
" v.pb(x%10);",
" x /= 10;",
" }while(x);",
" reverse(all(v));",
" for(auto itm:v)cout<<itm;",
" return cout;",
" }",
" ll pw2(ll x,int d,int p){",
" ll t = 1;",
" for(;d;d>>=1,x=x*x%p)if(d&1)t=t*x%p;",
" return t;",
" }",
" const int hash_S = 1919810;",
" const int hash_N = 1000005;",
" struct hash_table{",
" #define S hash_S",
" #define N hash_N",
" vector<int>used;",
" int sz=0,hd[S+5],id[N],nxt[N],w[N];",
" inline void ins(int k,int val){",
" int u=k%S;",
" for(int i=hd[u];i;i=nxt[i])if(id[i]==k)return (void)(w[i]=val);",
" ++sz,nxt[sz]=hd[u],w[sz]=val,id[sz]=k,hd[u]=sz;",
" used.push_back(u);",
" }",
" inline int qry(int k){",
" for (int i=hd[k%S];i;i=nxt[i])if(id[i]==k)return w[i];",
" return -1;",
" }",
" inline void clear(){",
" sz=0;",
" for(int i:used)hd[i]=0;",
" }",
" #undef S",
" #undef N",
" };",
" namespace Cipolla{",
" mt19937 rnd(0);",
" int p;",
" bool chk(int x){",
" return pw2(x,(p-1)/2,p)==1;",
" }",
" ll w;//虚数单位",
" struct C{",
" int x,y;",
" C(){x=0,y=0;}",
" C(int xx,int yy){x=xx,y=yy;}",
" };",
" C operator * (C x,C y){",
" return C(((ll)x.x*y.x+w*x.y%p*y.y)%p,((ll)x.y*y.x+(ll)x.x*y.y)%p);",
" }",
" int Sqrt(int n,int prm){",
" // 返回较小的根，如果无解返回 -1",
" // 需要保证 p 为奇素数",
" if(n==0)return 0;",
" p = prm;",
" if(!chk(n))return -1;",
" ll a;",
" while(1){",
" a = rnd()%(p-1)+1;",
" if(!chk((a*a-n+p)%p))break;",
" }",
" int d = (p+1)/2;",
" C ans(1,0);",
" C x(a,1);",
" w = (a*a-n+p)%p;",
" for(;d;d>>=1,x=x*x)if(d&1)ans=ans*x;",
" return min(ans.x,p-ans.x);",
" }",
" }",
" using Cipolla::Sqrt;",
" namespace Pollard_rho{",
" static mt19937_64 rnd(0);",
" vector<ll> rlt;",
" static constexpr array<int, 12> chkp = {2,3,5,7,11,13,17,19,23,29,31,37};",
" // < 3.8e18",
" lll big_pw(lll x,ll d,ll p){",
" lll t = 1;",
" for(;d;d>>=1,x=x*x%p)if(d&1)t=t*x%p;",
" return t;",
" }",
" bool miller_rabin(ll n){",
" if(n==1)assert(false);",
" if(n%2==0){",
" if(n==2)return 1;",
" return 0;",
" }",
" ll st = n-1;",
" while(!(st&1))st>>=1;",
" ll nw;",
" lll x;",
" for(auto pi:chkp){",
" if(pi==n)return 1;",
" nw = st;",
" x = big_pw(pi,st,n);",
" while(nw!=n-1&&x!=1&&x!=n-1){",
" x = x*x%n;",
" nw <<= 1;",
" }",
" if(x!=n-1&&(nw&1)==0)return 0;",
" }",
" return 1;",
" }",
" void rho(ll n){",
" if(miller_rabin(n)){",
" rlt.pb(n);",
" return ;",
" }",
" ll t,s,c,val;",
" ll d = n;",
" while(d==n){",
" c = rnd()%(n-1)+1;",
" s = t = 0;",
" val = 1;",
" for(int goal=1;;goal<<=1,s=t,val=1){",
" repp(stp,1,goal){",
" t = ((lll)t*t+c)%n;",
" val = ((lll)val*abs(t-s))%n;",
" if((stp%127)==0){",
" d = __gcd(val,n);",
" if(d>1)break;",
" }",
" }",
" d = __gcd(val,n);",
" if(d>1)break ;",
" }",
" }",
" rho(d);",
" rho(n/d);",
" return ;",
" }",
" vector<ll> factor(ll n){",
" rlt.clear();",
" if(n<=2000){",
" for(int i=2;i*i<=n;++i){",
" while(n%i==0){",
" rlt.pb(i);",
" n /= i;",
" }",
" }",
" if(n!=1)rlt.pb(n);",
" return rlt;",
" }",
" rho(n);",
" return rlt;",
" }",
" }",
" using Pollard_rho::factor, Pollard_rho::miller_rabin;",
" ll phi(ll n){",
" map<ll,int> mp;",
" auto v = factor(n);",
" for(auto x:v)mp[x]++;",
" ll rlt = 1;",
" for(auto [x,y] : mp){",
" rlt *= x-1;",
" rep(i,1,y)rlt *= x;",
" }",
" return rlt;",
" }",
" namespace PrmRoot{",
" bool chkRoot(ll p){",
" // 检测在模 p 意义下是否存在原根",
" if(p==2||p==4)return 1;",
" if(p%8==0)return 0;",
" if(p%2==0)p /= 2;",
" if(p%2==0)p /= 2;",
" if(miller_rabin(p))return 1;",
" int nw = 2;",
" int Poe = 2;",
" while(nw<p){",
" nw <<= 1;",
" ",
" Poe++;",
" }",
" return 0;",
" }",
" int getRoot(ll p){",
" // 要求 p 是素数 ，需要保证 p 是 2,4,p^k,2*p^k",
" // 模 p 意义下的最小原根",
" return ;",
" }",
" }",
" // namespace BSGS{",
" // static hash_table h;",
" // int nowp = 0;",
" // int inv = 0;",
" // void clear(){",
" // h.clear();",
" // return ;",
" // }",
" // void init(int p,int B){",
" // ll nw = 1;",
" // rep(i,0,B){",
" // h.ins(nw);",
" // nw = (nw*)",
" // }",
" // return ;",
" // }",
" // void log_p(int x,int p,int B=-1){",
" // if(B==-1)B = sqrt(p)+5;",
" // if(nowp!=p)init(p,B);",
" // nowp = p;",
" // }",
" // }",
" // using BSGS::log_p;",
"}",
]
},
"myDomtree" : {
"prefix" : "myDomtree",
"body" : [
"namespace Domtree{",
" vector<int> v[MAX];",
" vector<int> iv[MAX];//反图",
" vector<int> rechk[MAX];",
" array<int,3> pa[MAX];//<fa,mn,which>,并查集",
" int tpa[MAX];// 树上父亲",
" int ord[MAX];",
" int dfn[MAX];",
" int sdom[MAX],idom[MAX];",
" int tot = 0;",
" void clear(int sz){",
" tot = 0;",
" repp(i,0,sz)v[i].clear();",
" repp(i,0,sz)iv[i].clear();",
" repp(i,0,sz)rechk[i].clear();",
" memset(dfn,0,intsz*(sz+3));",
" return ;",
" }",
" array<int,3> mrg(array<int,3> x,array<int,3> y){",
" array<int,3> rlt;",
" rlt[0] = y[0];",
" if(y[1]<=x[1])rlt[1] = y[1],rlt[2] = y[2];",
" else rlt[1] = x[1],rlt[2] = x[2];",
" return rlt;",
" }",
" array<int,3> fd(int x){//并查集",
" if(x==pa[x][0])return pa[x];",
" return pa[x] = mrg(pa[x],fd(pa[x][0]));",
" }",
" void dfs(int x,int fa){",
" tpa[x] = fa;",
" ord[dfn[x] = ++tot] = x;",
" for(auto to:v[x])if(!dfn[to])dfs(to,x);",
" return ;",
" }",
" void adde(int x,int y){",
" v[x].pb(y);",
" iv[y].pb(x);",
" return ;",
" }",
" void getDom(int x){",
" dfs(x,x);",
" idom[x] = x;",
" int nw;",
" repp(i,1,tot){",
" nw = ord[i];",
" pa[nw] = {nw,i,nw},sdom[nw] = dfn[nw];",
" }",
" pper(i,tot,2){",
" nw = ord[i];",
" for(auto to:rechk[nw])idom[to] = fd(to)[2];",
" for(auto to:iv[nw]){",
" if(!dfn[to])continue;",
" sdom[nw] = min(sdom[nw],fd(to)[1]);",
" }",
" pa[nw][0] = tpa[nw];pa[nw][1] = sdom[nw];",
" idom[nw] = sdom[nw] = ord[sdom[nw]];",
" rechk[sdom[nw]].pb(nw);",
" }",
" repp(i,2,tot){",
" nw=ord[i];",
" if(sdom[nw]!=idom[nw])idom[nw] = idom[idom[nw]];",
" }",
" return ;",
" }",
"}",
"using Domtree::adde,Domtree::getDom,Domtree::idom;"
]
},
"mySAM" : {
"prefix" : "mySAM",
"body" : [
"struct SAM{",
" struct Node{",
" int pa;",
" int len;",
" int nxt[26];",
" int& operator [] (int x){",
" return nxt[x];",
" }",
" }t[MAX];",
" int tot = 0;",
" int cur = 0;",
" vector<int> v[MAX];",
" void clear(){",
" repp(i,0,tot){",
" v[i].clear();",
" t[i].pa = t[i].len = 0;",
" memset(t[i].nxt,0,sizeof(t[i].nxt));",
" }",
" return ;",
" }",
" void build(){",
" repp(i,1,tot){",
" v[t[i].pa].pb(i);",
" }",
" return ;",
" }",
" void ins(int x){",
" int lst = cur;",
" cur = ++tot;",
" t[cur].len = t[lst].len+1;",
" while(lst&&!t[lst][x]){",
" t[lst][x] = cur;lst = t[lst].pa;",
" }",
" int nxt = t[lst][x];",
" if(!nxt){",
" assert(lst==0);",
" t[cur].pa = nxt;",
" t[lst][x] = cur;",
" }else if(t[nxt].len==t[lst].len+1){",
" t[cur].pa = nxt;",
" }else{",
" int clone = ++tot;",
" t[clone] = t[nxt];",
" t[nxt].pa = clone;",
" t[cur].pa = clone;",
" t[clone].len = t[lst].len+1;",
" while(t[lst][x]==nxt){",
" t[lst][x] = clone;",
" lst = t[lst].pa;",
" }",
" }",
" return ;",
" }",
"}sam;",
]
}
"myPAM" : {
"prefix" : "mySAM",
"body" : [
"struct PAM{",
"\tstruct Node{",
"\t\tint fa,len,nxt[26];",
"\t\tint & operator [] (int x){",
"\t\t\treturn nxt[x];",
"\t\t}",
"\t}t[MAX];",
"\tstring s;",
"\tint tot,cur;",
"\tvoid init(){",
"\t\tmemset(t,0,sizeof(t[0])*(tot+2));",
"\t\ttot = cur = 1;",
"\t\tt[0].fa = 1,t[1].len = -1;",
"\t\treturn ;",
"\t}",
"\tint getfail(int pos,int i){",
"\t\twhile(s[i-t[pos].len-1]!=s[i])pos = t[pos].fa;",
"\t\treturn pos;",
"\t}",
"\tvoid build(string &S){",
"\t\tinit();",
"\t\ts = S;",
"\t\tint n = s.length()-1;",
"\t\trepp(i,1,n){",
"\t\t\tint c = s[i]-'a';",
"\t\t\tcur = getfail(cur,i);",
"\t\t\tif(!t[cur][c]){",
"\t\t\t\tt[++tot].fa = t[getfail(t[cur].fa,i)][c];",
"\t\t\t\tt[tot].len = t[cur].len+2;",
"\t\t\t\tt[cur][c] = tot;",
"\t\t\t}",
"\t\t\tcur = t[cur][c];",
"\t\t}",
"\t\treturn ;",
"\t}",
"}pam;",
]
}
}