板子集合
贴一些不熟练的板子
#include<cstdio>
const int mod=998244353,maxn=1<<18;
int T,n;
long long g[maxn],f[maxn],gr[maxn],w[2][maxn+1];
long long power(long long a,long long b){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
void fft(long long a[],int tt,int op)
{
int i,j,k,l;
static long long aa[maxn];
for(i=0;i<tt;i++)
{
for(l=0,j=i,k=1;k<tt;k<<=1,j>>=1)l=(l<<1)+(j&1);
aa[l]=a[i];
}
for(i=2;i<=tt;i<<=1)
for(j=0;j<tt;j+=i)
for(k=0;k<(i>>1);k++)
{
long long u=aa[j+k],v=aa[j+k+(i>>1)]*w[op][maxn/i*k]%mod;
aa[j+k]=(u+v)%mod;
aa[j+k+(i>>1)]=(u-v+mod)%mod;
}
if(op)
{
int tr=power(tt,mod-2);
for(i=0;i<tt;i++)aa[i]=aa[i]*tr%mod;
}
for(i=0;i<tt;i++)a[i]=aa[i];
}
void inv(long long a[],long long ar[],int t)
{
int i,j,k;
static long long aa[maxn];
if(t==1){ar[0]=power(a[0],mod-2);return;}
inv(a,ar,t>>1);
for(k=1;k<(t<<1);k<<=1);
for(j=0;j<t;j++)aa[j]=a[j];for(j=t;j<k;j++)aa[j]=0;
fft(ar,k,0);fft(aa,k,0);
for(j=0;j<k;j++)aa[j]=(2-ar[j]*aa[j]%mod+mod)%mod;
for(j=0;j<k;j++)ar[j]=ar[j]*aa[j]%mod;
fft(ar,k,1);
for(i=t;i<k;i++)ar[i]=0;
}
int main()
{
int i,j,k;
w[0][0]=1;
long long tt=power(3,(mod-1)/maxn);
for(i=1;i<=maxn;i++)w[0][i]=w[0][i-1]*tt%mod;
for(i=0;i<=maxn;i++)w[1][i]=w[0][maxn-i];
g[0]=1;
for(i=1;i<=maxn;i++)g[i]=g[i-1]*i%mod;
inv(g,gr,maxn/2);
for(i=0;i<=maxn/2;i++)f[i]=(mod-gr[i])%mod;
f[0]++;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%lld\n",f[n]);
}
return 0;
}
#include<cstdio>
#include<cstring>
char s[100011];
int n,sa[200001],rank[200001],tsa[200001],trank[200001],h[200001];
int a[200001];
int main()
{
int i,j,k,p;
scanf("%s",s+1);n=strlen(s+1);
for(i=1;i<=n;i++)trank[i]=s[i]-'a';
for(i=1;i<=n;i++)a[trank[i]]++;
for(i=1;i<26;i++)a[i]+=a[i-1];
for(i=n;i>0;i--)sa[a[trank[i]]--]=i;
rank[sa[1]]=p=1;
for(i=2;i<=n;i++)
{
if(trank[sa[i]]!=trank[sa[i-1]])p++;
rank[sa[i]]=p;
}
for(i=1;i<=n;i<<=1)
{
memset(a,0,sizeof(a));
for(j=1;j<=n;j++)a[rank[j+i]]++;
for(j=1;j<=p;j++)a[j]+=a[j-1];
for(j=n;j>0;j--)tsa[a[rank[j+i]]--]=j;
memset(a,0,sizeof(a));
for(j=1;j<=n;j++)a[rank[j]]++;
for(j=1;j<=p;j++)a[j]+=a[j-1];
for(j=n;j>0;j--)sa[a[rank[tsa[j]]]--]=tsa[j];
trank[sa[1]]=p=1;
for(j=2;j<=n;j++)
{
if(rank[sa[j]]!=rank[sa[j-1]]||rank[sa[j]+i]!=rank[sa[j-1]+i])p++;
trank[sa[j]]=p;
}
for(j=1;j<=n;j++)rank[j]=trank[j];
}
for(i=1,j=0;i<=n;i++)
{
if(rank[i]==1)continue;
while(s[i+j]==s[sa[rank[i]-1]+j])j++;
h[rank[i]]=j;
if(j>0)j--;
}
for(i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
for(i=2;i<=n;i++)printf("%d ",h[i]);puts("");
return 0;
}
#include<cstdio>
int n,c;
int a[100001];
int head[100001],end[200001],next[200001],tp=0;
int deg[100001];
int son[11][4000001],fail[4000001],len[4000001],last=1,tt=1;
long long gs[4000001];
void add(int ch)
{
int i,j,k;
if(son[ch][last])
{
i=last;j=son[ch][last];
if(len[j]==len[i]+1)last=j;else
{
++tt;len[tt]=len[i]+1;for(k=0;k<c;k++)son[k][tt]=son[k][j];
fail[tt]=fail[j];
for(;i&&son[ch][i]==j;i=fail[i])son[ch][i]=tt;
fail[j]=tt;last=tt;
}
}
else
{
int cur=++tt;len[tt]=len[last]+1;
for(i=last;i&&!son[ch][i];i=fail[i])son[ch][i]=tt;
if(!i)fail[tt]=1;else
{
j=son[ch][i];
if(len[i]+1==len[j])fail[tt]=j;else
{
++tt;len[tt]=len[i]+1;for(k=0;k<c;k++)son[k][tt]=son[k][j];
fail[tt]=fail[j];
for(;i&&son[ch][i]==j;i=fail[i])son[ch][i]=tt;
fail[j]=tt;fail[cur]=tt;
}
}
last=cur;
}
}
void dfs(int p,int d)
{
int i,j,k;
add(a[p]);
int t=last;
for(i=head[p];i;i=next[i])if(end[i]!=d)
{
dfs(end[i],p);last=t;
}
}
void dfs2(int p)
{
int i,j,k;
if(gs[p])return;
//printf("p=%d\n",p);
for(i=0;i<c;i++)if(son[i][p]){dfs2(son[i][p]);gs[p]+=gs[son[i][p]];}
gs[p]++;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&c);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
next[++tp]=head[x];head[x]=tp;end[tp]=y;
next[++tp]=head[y];head[y]=tp;end[tp]=x;
deg[x]++;deg[y]++;
}
for(i=1;i<=n;i++)if(deg[i]==1){last=1;dfs(i,i);}
//puts("ok");
dfs2(1);
printf("%lld\n",gs[1]-1);
return 0;
}
#include<cstdio>
#include<algorithm>
int rev[150001],mx[150001],c[150001],dad[150001],son[150001][2];
int st[150001],tp=0;
int isroot(int p){return son[dad[p]][0]!=p&&son[dad[p]][1]!=p;}
void reverse(int p)
{
rev[p]^=1;int t=son[p][0];son[p][0]=son[p][1];son[p][1]=t;
rev[son[p][0]]^=1;rev[son[p][1]]^=1;
}
void upd(int p)
{
mx[p]=p;
if(c[mx[son[p][0]]]>c[mx[p]])mx[p]=mx[son[p][0]];
if(c[mx[son[p][1]]]>c[mx[p]])mx[p]=mx[son[p][1]];
}
void rot(int p)
{
int d=dad[p],dd=dad[dad[p]];
int t=son[d][1]==p;
if(!isroot(d))son[dd][son[dd][1]==d]=p;
son[d][t]=son[p][!t];son[p][!t]=d;
dad[p]=dd;dad[d]=p;dad[son[d][t]]=d;
upd(d);upd(p);
printf("p=%d d=%d\n",p,d);
}
void splay(int p)
{
int i;
tp=0;st[++tp]=p;
for(i=p;!isroot(i);i=dad[i])st[++tp]=dad[i];
while(tp){if(rev[st[tp]])reverse(st[tp]);tp--;}
while(!isroot(p))
{
if(!isroot(dad[p]))
{
if((son[dad[p]][0]==p)^(son[dad[dad[p]]][0]==dad[p]))rot(p);else rot(dad[p]);
}
upd(p);rot(p);
}
}
void access(int p){int i=0;for(;p;p=dad[p]){splay(p);son[p][1]=i;i=p;upd(p);}}
void makeroot(int p){access(p);splay(p);rev[p]^=1;}
void link(int x,int y){makeroot(x);dad[x]=y;}
void cut(int x,int y){makeroot(x);access(y);splay(y);son[y][0]=0;dad[x]=0;}
int fmax(int x,int y){makeroot(x);access(y);splay(y);return mx[y];}
int n,m;
int ans=1<<30;
struct mjj{int x,y,a,b;}a[100001];
int fa[50001];
int find(int p){return p==fa[p]?p:fa[p]=find(fa[p]);}
int cmp(mjj a,mjj b){return a.a<b.a;}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
std::sort(a+1,a+m+1,cmp);
for(i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++)
{
if(find(a[i].x)!=find(a[i].y))
{
fa[fa[a[i].x]]=fa[a[i].y];
c[n+i]=a[i].b;mx[n+i]=n+i;
link(n+i,a[i].x);link(n+i,a[i].y);
}
else
{
int t=fmax(a[i].x,a[i].y);
if(c[t]>a[i].b)
{
cut(t,a[t-n].x);cut(t,a[t-n].y);
c[n+i]=a[i].b;mx[n+i]=n+i;
link(n+i,a[i].x);link(n+i,a[i].y);
}
}
if(find(1)==find(n))
{
int t=fmax(1,n);
if(c[t]+a[i].a<ans)ans=c[t]+a[i].a;
}
}
if(ans==1<<30)puts("-1");else printf("%d\n",ans);
return 0;
}
#include<cstdio>
#include<cmath>
#include<cstdlib>
#define double long double
const double eps=1e-9;
int n,m,ta;
double c[21];
double a[21][42];
int b[21],wz[42];
double x[42];
void pivot(int fr,int to,int mgs,int gs)
{
int i,j,k;
double t=a[to][fr];
for(j=0;j<=gs;j++)a[to][j]/=-t;
a[to][b[to]]=1/t;a[to][fr]=0;
wz[b[to]]=0;b[to]=fr;wz[fr]=to;
for(i=0;i<=mgs;i++)if(i!=to)
{
double t=a[i][fr];a[i][fr]=0;
for(j=0;j<=gs;j++)a[i][j]+=t*a[to][j];
}
}
double solve(int mgs,int gs)
{
int i,j,k;
while(1)
{
//for(i=0;i<=mgs;i++)
//{for(j=0;j<=gs;j++)printf("%lf ",a[i][j]);puts("");}puts("");
for(i=1,j=0;i<=gs;i++)if(!wz[i]&&a[0][i]>eps&&(!j||(rand()&1)))j=i;
if(!j)return a[0][0];
double t=1.0/0;k=0;
for(i=1;i<=mgs;i++)if(a[i][j]<-eps)
{
if(-a[i][0]/a[i][j]<t){t=-a[i][0]/a[i][j];k=i;}
}
if(k==0)return 1.0/0;
pivot(j,k,mgs,gs);
}
}
int main()
{
int i,j,k;
scanf("%d%d%d",&n,&m,&ta);
for(i=1;i<=n;i++)scanf("%Lf",&c[i]);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++){scanf("%Lf",&a[i][j]);a[i][j]=-a[i][j];}
scanf("%Lf",&a[i][0]);
b[i]=n+i;wz[n+i]=i;
}
for(i=1;i<=m;i++)a[i][n+m+1]=1;
a[0][n+m+1]=-1;
j=1;
for(i=2;i<=m;i++)if(a[i][0]<a[j][0])j=i;
if(a[j][0]<-eps)pivot(n+m+1,j,m,n+m+1);
double ans=solve(m,n+m+1);
if(ans<-eps){puts("Infeasible");return 0;}
if(wz[n+m+1])
{
for(i=1;i<=n+m;i++)if(!wz[i]&&fabs(a[0][i])>eps)
{
pivot(i,wz[n+m+1],m,n+m+1);
break;
}
}
for(i=0;i<=n+m;i++)a[0][i]=0;
for(i=1;i<=n;i++)
{
if(!wz[i])a[0][i]+=c[i];else
{
for(j=0;j<=n+m;j++)a[0][j]+=c[i]*a[wz[i]][j];
}
}
for(i=0;i<=m;i++)a[i][n+m+1]=0;
ans=solve(m,n+m);
if(ans<=1e100)
{
printf("%.10Lf\n",a[0][0]);
if(ta)
{
for(i=1;i<=m;i++)x[b[i]]=a[i][0];
for(i=1;i<=n;i++)printf("%.10Lf ",x[i]);puts("");
}
}
else puts("Unbounded");
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
int n,m;
int head[501],end[250001],next[250001],tp=-1;
int pp[501],vis[501],a[501],dad[501],pre[501],vis2[501],tim;
int ans;
int q[501],hh=1,tt=0;
int find(int p){return p==dad[p]?p:dad[p]=find(dad[p]);}
int lca(int x,int y)
{
tim++;
for(;;x=pre[pp[x]])
{
x=find(x);
vis2[x]=tim;
//printf("x=%d\n",x);
if(!pp[x])break;
}
//printf("tim=%d\n",tim);
//puts("ok3");
for(;;y=pre[pp[y]])
{
y=find(y);
if(vis2[y]==tim)break;
//printf("y=%d vis2[y]=%d\n",y,vis2[y]);
//system("pause");
}
return y;
}
void join(int x,int y)
{
for(;x!=y;x=pre[pp[x]])
{
int t=pp[x];
if(find(pre[t])!=find(y))pre[pre[t]]=t;
if(vis[t]==2){vis[t]=1;q[++tt]=t;}
if(vis[pre[t]]==2){vis[pre[t]]=1;q[++tt]=pre[t];}
dad[find(t)]=find(pre[t]);
dad[find(x)]=find(t);
}
}
int bfs(int p)
{
int i,j,k;
memset(vis,0,sizeof(vis));memset(a,0,sizeof(a));
for(i=1;i<=n;i++)dad[i]=i;
hh=1;tt=0;
q[++tt]=p;vis[p]=1;
while(hh<=tt)
{
//printf("q[hh]=%d\n",q[hh]);
for(i=head[q[hh]];i>=0;i=next[i])
{
//printf("end[i]=%d\n",end[i]);
if(find(end[i])==find(q[hh])||end[i]==pp[q[hh]])continue;
if(!vis[end[i]])
{
if(pp[end[i]])
{
vis[end[i]]=2;vis[pp[end[i]]]=1;pre[end[i]]=q[hh];
q[++tt]=pp[end[i]];
}
else
{
//puts("ok");
pre[end[i]]=q[hh];
for(j=end[i];pre[j]!=p;)
{
k=pp[pre[j]];
pp[j]=pre[j];pp[pre[j]]=j;
j=k;
}
pp[j]=p;pp[p]=j;
return 1;
}
}
else if(vis[end[i]]==1)
{
//puts("ok2");
int t=lca(q[hh],end[i]);
if(find(q[hh])!=find(t))pre[q[hh]]=end[i];
if(find(end[i])!=find(t))pre[end[i]]=q[hh];
join(q[hh],t);
join(end[i],t);
}
}
hh++;
}
return 0;
}
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
next[++tp]=head[x];head[x]=tp;end[tp]=y;
next[++tp]=head[y];head[y]=tp;end[tp]=x;
}
for(i=1;i<=n;i++)if(!pp[i])
{
ans+=bfs(i);
}
printf("%d\n",ans);
for(i=1;i<=n;i++)printf("%d ",pp[i]);
return 0;
}
#include<cstdio>
long long n;
int mod;
int p[100001],tp=0,cnt[100001],pc[100001];
long long power(long long a,long long b,long long mod){long long ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
long long fac(long long a,int q,long long &cs)
{
long long s=1;
long long ans=1;
long long ss=a/pc[q],rm=a%pc[q];
int i;
if(a==0)return 1;
for(i=1;i<=pc[q];i++)if(i%p[q]!=0)s=s*i%pc[q];
ans=power(s,ss,pc[q]);
for(i=1;i<=rm;i++)if(i%p[q]!=0)ans=ans*i%pc[q];
ans=ans*fac(a/p[q],q,cs)%pc[q];
cs+=a/p[q];
return ans;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(b==0){x=1;y=0;return a;}
long long r=exgcd(b,a%b,x,y);
long long t=x;x=y;y=t-a/b*y;
return r;
}
long long C(long long a,long long b)
{
int i;
long long ans=0;
for(i=1;i<=tp;i++)
{
long long ta=0,tb=0,tab=0;
long long aa=fac(a,i,ta),ab=fac(b,i,tb),aab=fac(a-b,i,tab);
long long nb,nab,tt;
exgcd(ab,pc[i],nb,tt);while(nb<0)nb+=pc[i];
exgcd(aab,pc[i],nab,tt);while(nab<0)nab+=pc[i];
long long tans=aa*nb%pc[i]*nab%pc[i]*power(p[i],ta-tb-tab,pc[i])%pc[i];
long long nans;
exgcd(mod/pc[i],pc[i],nans,tt);while(nans<0)nans+=pc[i];
ans=(ans+tans*nans%mod*(mod/pc[i])%mod)%mod;
}
return ans;
}
int main()
{
int i,j,k;
//freopen("T3.in","r",stdin);freopen("T3.out","w",stdout);
scanf("%lld%d",&n,&mod);
n--;
if(n==0){puts("1");return 0;}
long long t=mod;
for(i=2;i*i<=mod;i++)if(t%i==0)
{
p[++tp]=i;pc[tp]=1;
while(t%i==0){cnt[tp]++;pc[tp]*=i;t/=i;}
}
if(t>1){p[++tp]=t;cnt[tp]=1;pc[tp]=t;}
printf("%lld\n",(C(2*n,n)-C(2*n,n-1)+mod)%mod);
return 0;
}
评论 (0)