#include<bits/stdc++.h> #define MAXN 240005 #define MOD 998244353 #define invG 332748118 //G的逆元 #define G 3 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inlineintksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } staticint r[MAXN],a[MAXN],b[MAXN]; inlinevoidNTT(int *A,int n,int type){ for (registerint i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (registerint i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?G:invG,(MOD-1)/R); for (registerint j=0;j<n;j+=R){ int g=1; for (registerint k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } } char s1[MAXN],s2[MAXN]; int ans[MAXN]; intmain(){ int n=read(); scanf("%s%s",s1+1,s2+1); for (registerint i=1;i<=n;++i) a[i-1]=s1[n-i+1]-'0'; for (registerint i=1;i<=n;++i) b[i-1]=s2[n-i+1]-'0'; int m=1,L=0; while (m<=2*n) m<<=1,L++; for (registerint i=0;i<=m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } NTT(a,m,1),NTT(b,m,1); for (registerint i=0;i<=m;++i) a[i]=(1ll*a[i]*b[i])%MOD; NTT(a,m,-1); int inv=ksm(m,MOD-2); for (registerint i=0;i<=m;++i){ ans[i]+=(1ll*a[i]*inv)%MOD;//要乘上m的逆元 ans[i+1]+=ans[i]/10,ans[i]%=10; } while (ans[m]==0) m--; for (registerint i=m;i>=0;--i) putchar(ans[i]+'0'); }
#include<bits/stdc++.h> #define MAXN 1000005 #define MOD 998244353 #define invG 332748118 #define G 3 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inlineintksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } int r[MAXN],C[MAXN]; inlinevoidNTT(int *A,int n,int type){ for (registerint i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (registerint i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?G:invG,(MOD-1)/R); for (registerint j=0;j<n;j+=R){ int g=1; for (registerint k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } } inlineintget_inv(int x){ returnksm(x,MOD-2); } int m,L; inlinevoidInit(int len){ m=1,L=0; while (m<2*len) m<<=1,L++; for (registerint i=0;i<m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } } inlinevoidInv(int *A,int *B,int len){ if (len==1){ B[0]=get_inv(A[0]); return ; } Inv(A,B,(len+1)>>1);//注意是向上取整 Init(len); for (registerint i=0;i<len;++i) C[i]=A[i];//只用前面一部分 for (registerint i=len;i<m;++i) C[i]=0; NTT(C,m,1),NTT(B,m,1); for (registerint i=0;i<m;++i){ B[i]=(2ll-1ll*B[i]*C[i]%MOD+MOD)*B[i]%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (registerint i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD;//推完之后B'->B for (registerint i=len;i<m;++i) B[i]=0;//多出来的部分要舍去 } int F[MAXN],Ans[MAXN]; intmain(){ int n=read(); for (registerint i=0;i<n;++i) F[i]=read(); Inv(F,Ans,n); for (registerint i=0;i<n;++i) printf("%d ",Ans[i]); }
#include<bits/stdc++.h> #define MAXN 1000005 #define MOD 998244353 #define invG 332748118 #define G 3 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inlineintksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } int r[MAXN],C[MAXN]; inlinevoidNTT(int *A,int n,int type){ for (registerint i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (registerint i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?G:invG,(MOD-1)/R); for (registerint j=0;j<n;j+=R){ int g=1; for (registerint k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } } inlineintget_inv(int x){ returnksm(x,MOD-2); } int m,L; inlinevoidInit(int len){ m=1,L=0; while (m<2*len) m<<=1,L++; for (registerint i=0;i<m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } } inlinevoidInv(int *A,int *B,int len){ if (len==1){ B[0]=get_inv(A[0]); return ; } Inv(A,B,(len+1)>>1); Init(len); for (registerint i=0;i<len;++i) C[i]=A[i]; for (registerint i=len;i<m;++i) C[i]=0; NTT(C,m,1),NTT(B,m,1); for (registerint i=0;i<m;++i){ B[i]=(2ll-1ll*B[i]*C[i]%MOD+MOD)*B[i]%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (registerint i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD; for (registerint i=len;i<m;++i) B[i]=0; } int F[MAXN],Ans[MAXN]; intmain(){ int n=read(); F[0]=1; for (registerint i=1;i<n;++i) F[i]=(-read()+MOD)%MOD; Inv(F,Ans,n); for (registerint i=0;i<n;++i) printf("%d ",Ans[i]); }
#include<bits/stdc++.h> #define MAXN 1000005 #define MOD 998244353 #define invG 332748118 #define G 3 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inlineintksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } int r[MAXN],C[MAXN]; inlinevoidNTT(int *A,int n,int type){ for (registerint i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (registerint i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?G:invG,(MOD-1)/R); for (registerint j=0;j<n;j+=R){ int g=1; for (registerint k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } } inlineintget_inv(int x){ returnksm(x,MOD-2); } int m,L; inlinevoidInit(int len){ m=1,L=0; while (m<2*len) m<<=1,L++; for (registerint i=0;i<m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } } inlinevoidInv(int *A,int *B,int len){ if (len==1){ B[0]=get_inv(A[0]); return ; } Inv(A,B,(len+1)>>1); Init(len); for (registerint i=0;i<len;++i) C[i]=A[i]; for (registerint i=len;i<m;++i) C[i]=0; NTT(C,m,1),NTT(B,m,1); for (registerint i=0;i<m;++i){ B[i]=(2ll-1ll*B[i]*C[i]%MOD+MOD)*B[i]%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (registerint i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD; for (registerint i=len;i<m;++i) B[i]=0; } int D[MAXN],inv2; inlinevoidSqrt(int *A,int *B,int len){ if (len==1){ B[0]=A[0]; return ;//保证a_0=1 } Sqrt(A,B,(len+1)>>1); for (registerint i=0;i<(len<<1);++i) D[i]=0; Inv(B,D,len);//得出B^-1(x) Init(len); for (registerint i=0;i<len;++i) C[i]=A[i]; for (registerint i=len;i<m;++i) C[i]=0; NTT(B,m,1),NTT(C,m,1),NTT(D,m,1);//B:目标 C:A(x) D:B^-1(x) //注意要做三次NTT for (registerint i=0;i<m;++i){ B[i]=1ll*inv2*(1ll*C[i]*D[i]%MOD+B[i])%MOD; } NTT(B,m,-1); int inv=get_inv(m); for (registerint i=0;i<len;++i) B[i]=(1ll*B[i]*inv)%MOD; for (registerint i=len;i<m;++i) B[i]=0; } int F[MAXN],Ans[MAXN]; intmain(){ inv2=ksm(2,MOD-2); int n=read(); for (registerint i=0;i<n;++i) F[i]=read(); Sqrt(F,Ans,n); for (registerint i=0;i<n;++i) printf("%d ",Ans[i]); }
#include<bits/stdc++.h> #define MAXN 2000005 #define MOD 1004535809 #define invG 334845270 #define G 3 #define int long long usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } inlineintksm(int b,int k){ int ans=1; while (k){ if (k&1) ans=(1ll*ans*b)%MOD; b=(1ll*b*b)%MOD; k>>=1; } return ans; } inlineintget_inv(int x){ returnksm(x,MOD-2); } int r[MAXN],C[MAXN]; inlinevoidNTT(int *A,int n,int type){ for (registerint i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (registerint i=1;i<n;i<<=1){ int R=i<<1; int Gn=ksm(type==1?G:invG,(MOD-1)/R); for (registerint j=0;j<n;j+=R){ int g=1; for (registerint k=0;k<i;++k,g=(1ll*g*Gn)%MOD){ int x=A[j+k],y=(1ll*g*A[i+j+k])%MOD; A[j+k]=(x+y)%MOD,A[i+j+k]=(x-y+MOD)%MOD; } } } if (type==1) return ; int inv=get_inv(n); for (registerint i=0;i<n;++i){ A[i]=1ll*A[i]*inv%MOD; } } int m,L; inlinevoidInitNTT(int len){ m=1,L=0; while (m<2*len) m<<=1,L++; for (registerint i=0;i<m;++i){ r[i]=(r[i>>1]>>1|((i&1)<<(L-1))); } } inlinevoidInv(int *A,int *B,int len){ if (len==1){ B[0]=get_inv(A[0]); return ; } Inv(A,B,(len+1)>>1); InitNTT(len); for (registerint i=0;i<len;++i) C[i]=A[i]; for (registerint i=len;i<m;++i) C[i]=0; NTT(C,m,1),NTT(B,m,1); for (registerint i=0;i<m;++i){ B[i]=((2ll-1ll*B[i]*C[i]%MOD+MOD)*B[i]%MOD+MOD)%MOD; } NTT(B,m,-1); for (registerint i=len;i<m;++i) B[i]=0; } int F[MAXN]; int A[MAXN],B[MAXN],Ans[MAXN]; int fac[MAXN],inv_fac[MAXN],n; int inv2=ksm(2,MOD-2); //F=A*B^-1 inlineintCalc(int x){ return1ll*x*(x-1)/2;//不能取模,要取也只能是MOD-1 } inlinevoidInit(){ fac[0]=1; for (registerint i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%MOD; for (registerint i=0;i<=n;++i) inv_fac[i]=ksm(fac[i],MOD-2); } #undef int intmain(){ #define int long long n=read(); Init(); for (registerint i=1;i<=n;++i){ A[i]=1ll*ksm(2,Calc(i))*inv_fac[i-1]%MOD; } for (registerint i=0;i<=n;++i){ B[i]=1ll*ksm(2,Calc(i))*inv_fac[i]%MOD; } InitNTT(n); Inv(B,Ans,m); InitNTT(n); NTT(A,m,1);NTT(Ans,m,1); for (registerint i=0;i<m;++i) A[i]=1ll*A[i]*Ans[i]%MOD; NTT(A,m,-1); printf("%lld\n",1ll*A[n]*fac[n-1]%MOD); }