• 欢迎光临~

# A. 体育测试

(f_{i,j}) 表示前 (i) 个位置选了 (j) 个二类点的方案数

(dp) 时只考虑二类点，在有一类点结束时再乘上贡献的系数

Code
``````#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 1000000007
#define debug(args...) fprintf(stderr,args);
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n;
int a[5010],num[5010];
int p1[5010],p2[5010];
int f[5010][5010];
int fac[5010],inv[5010];
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
return res;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
inv[0]=fac[0]=1;for(int i=1;i<=5000;i++) fac[i]=fac[i-1]*i%mod,inv[i]=inv[i-1]*qpow(i,mod-2)%mod;
for(int i=1;i<=n;i++) p2[i]+=p2[i-1],p1[i]+=p1[i-1];f[0][0]=1;
for(int i=1,k;i<=n;i++) for(int j=0;j<=p2[i]&&j<=i;j++){
f[i][j]+=f[i-1][j];
if(j) f[i][j]+=f[i-1][j-1]*(p2[i]-j+1);
k=i-j-p1[i-1];
f[i][j]%=mod;
if(k>=p1[i]-p1[i-1]) f[i][j]=f[i][j]*C(k,p1[i]-p1[i-1])%mod*fac[p1[i]-p1[i-1]]%mod;
else f[i][j]=0;
}
printf("%lldn",f[n][p2[n]]);
return 0;
}
``````

# B. 贸易

Code
``````#include<bits/stdc++.h>
#define int long long
#define rint signed
#define LLL(args...) fprintf(stderr,args)
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,rt,S,mxd,inv;
int siz[100010],mx[100010];
int dis[262150],val[100010];
bool vis[100010];
struct QUE{int a,b,x;}LL[100010];
vector<int>a,F,A,ANS;
inline void md(int &x){x=(x>=mod)?x-mod:x;}
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
return res;
}
namespace POLY{
int inv;
vector<int> r,g,T,Q[400010];
inline void init(int len,int L){
for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
g[0]=1,g[1]=qpow(3,(mod-1)/len);for(int i=2;i<len;i++) g[i]=g[i-1]*g[1]%mod;
}
inline void rev(int len){g[0]=1,g[1]=qpow(g[1],mod-2);for(int i=2;i<len;i++) g[i]=g[i-1]*g[1]%mod;}
inline void ntt(vector<int> &a,int len){
for(int i=0;i<len;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int d=1,t=len>>1;d<len;d<<=1,t>>=1) for(int i=0;i<len;i+=(d<<1)) for(int j=0;j<d;j++){
int tmp=g[t*j]*a[i+j+d]%mod;
md(a[i+j+d]=a[i+j]-tmp+mod);
md(a[i+j]=a[i+j]+tmp);
}
}
inline vector<int> Mul(vector<int> F,vector<int> G){
int len,L,siz;
siz=F.size()+G.size()-1;
for(len=1,L=0;len<siz;len<<=1,L++);init(len,L);
F.resize(len);G.resize(len);
ntt(F,len);ntt(G,len);rev(len);
for(int i=0;i<len;i++) F[i]=F[i]*G[i]%mod;
ntt(F,len);inv=qpow(len,mod-2);
for(int i=0;i<len;i++) F[i]=F[i]*inv%mod;
return F;
}
inline vector<int> Mult(vector<int> F,vector<int> G){
int n=F.size(),m=G.size();
reverse(G.begin(),G.end());G=Mul(F,G);
for(int i=0;i<n;i++) F[i]=G[i+m-1];
return F;
}
inline vector<int> INV(vector<int> F,int n){
vector<int>G;G.resize(1);
G[0]=qpow(F[0],mod-2);int len,L;
for(L=1,len=2;(len>>1)<n;){
for(int i=0;i<len;i++) T[i]=F[i];
len<<=1,L++;init(len,L);
for(int i=len>>1;i<len;i++) T[i]=0;G.resize(len);
ntt(G,len);ntt(T,len);rev(len);
for(int i=0;i<len;i++) G[i]=(2ll-T[i]*G[i]%mod+mod)%mod*G[i]%mod;
ntt(G,len);inv=qpow(len,mod-2);
for(int i=len>>1;i<len;i++) G[i]=0;
for(int i=0,lim=len>>1;i<lim;i++) G[i]=G[i]*inv%mod;
}
for(int i=n;i<len;i++) G[i]=0;
return G;
}
#define lson rt<<1
#define rson rt<<1|1
void init(vector<int> &a,int rt,int l,int r){
if(l==r){Q[rt].resize(2);Q[rt][0]=1,Q[rt][1]=mod-a[l];return ;}
int mid=(l+r)>>1;
init(a,lson,l,mid);init(a,rson,mid+1,r);
Q[rt]=Mul(Q[lson],Q[rson]);
}
void multi(int rt,int l,int r,vector<int> f,vector<int> &g){
f.resize(r-l+1);
if(l==r) return g[l]=f[0],void();
int mid=(l+r)>>1;
multi(lson,l,mid,Mult(f,Q[rson]),g);
multi(rson,mid+1,r,Mult(f,Q[lson]),g);
}
void multipoint(vector<int> f,vector<int> a,vector<int> &ans,int n){
f.resize(n+1);a.resize(n);
init(a,1,0,n-1);ans.resize(n);
multi(1,0,n-1,Mult(f,INV(Q[1],n+1)),ans);
}
inline void INIT(){T.resize(524290);r.resize(524290);g.resize(524290);}
#undef lson
#undef rson
}
void getrt(int x,int fa){
siz[x]=1;mx[x]=0;
int y=ver[i];
if(y==fa||vis[y]) continue;
getrt(y,x);
siz[x]+=siz[y];
mx[x]=max(mx[x],siz[y]);
}
mx[x]=max(mx[x],S-siz[x]);
if(mx[x]<mx[rt]) rt=x;
}
void dfs(int x,int fa,int dep){
a[dep]++;mxd=max(mxd,dep);
int y=ver[i];
if(y==fa||vis[y]) continue;
dfs(y,x,dep+1);
}
}
void calc(int x,int dep,int opt){
mxd=0;dfs(x,0,dep);
int len=1,L=0;
for(;len<=mxd+mxd;len<<=1,L++);POLY::init(len,L);
POLY::ntt(a,len);POLY::rev(len);
for(int i=0;i<len;i++) a[i]=a[i]*a[i]%mod;
POLY::ntt(a,len);POLY::inv=qpow(len,mod-2);
for(int i=0;i<len;i++) a[i]=a[i]*POLY::inv%mod;
for(int i=0;i<len;i++) dis[i]+=opt*a[i],a[i]=0;
}
void solve(int x){
vis[x]=1;calc(x,0,1);
int y=ver[i];
if(vis[y]) continue;
calc(y,1,-1);
S=siz[y];mx[rt=0]=inf;
getrt(y,0);solve(rt);
}
}
inline void pre(){
F.resize(n+1);A.resize(m);
for(int i=0;i<=n;i++) F[i]=dis[i];
for(int i=0;i<m;i++) A[i]=LL[i+1].x;
}
inline int calc(int x){
int res=0;
for(int i=0,base=1;i<=n;i++,base=base*x%mod){
if(!dis[i]) break;
md(res=(res+base*dis[i]%mod));
}
return res;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
for(int i=1,x,y;i<n;i++){
}
S=n;mx[rt=0]=inf;
getrt(1,0);solve(rt);
for(int i=1,x,y;i<=m;i++){
}
pre();POLY::multipoint(F,A,ANS,max(n+1,m));
for(int i=0,res;i<m;i++){
res=LL[i+1].b*ANS[i]%mod*qpow(n*n%mod,mod-2)%mod;
md(res=(res-LL[i+1].a+mod));
printf("%lldn",res);
}
return 0;
}
``````

# C. 密码

Code
``````#include "password.h"
#include<bits/stdc++.h>
#define debug(args...) fprintf(stderr,args)
using namespace std;
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<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int N,t[2100];
bool res[2100];
bitset<2100>B[2100],T[2100],TT[2100],now;
inline void ins(int id){
TT[id][id]=1;
for(int i=1;i<=N;i++) if(B[id][i]==1){
if(t[i]) B[id]^=T[i],TT[id]^=TT[t[i]];
else{t[i]=id;T[i]=B[id];break;}
}
}
void encoder(int n,int m,int k,const char* a,const char* b,char* ans){
mt19937 rd(998244353);
N=n;
for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) B[j][i]=rd()%2;
for(int i=1;i<=n;i++) if(a[i-1]=='1') now[i]=1;
for(int i=1;i<=m;i++) if(b[i-1]=='1') now^=B[i];else if(b[i-1]=='?') ins(i);
for(int i=1;i<=n;i++) if(now[i]==0){now^=T[i];for(int j=1;j<=m;j++) res[j]^=TT[t[i]][j];}
for(int i=1;i<=m;i++) if(b[i-1]=='?') ans[i-1]=res[i]+'0';else ans[i-1]=b[i-1];
}
void decoder(int n,int m,const char* a,char* ans){
mt19937 rd(998244353);now.reset();
for(int i=1;i<=n;i++) now[i]=1;
for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) B[j][i]=rd()%2;
for(int i=1;i<=m;i++) if(a[i-1]=='1') now^=B[i];
for(int i=1;i<=n;i++) ans[i-1]=now[i]+'0';
}
``````

Code
``````#include "password.h"
#include<bits/stdc++.h>
#define debug(args...) fprintf(stderr,args)
using namespace std;
void encoder(int n,int m,int k,const char* a,const char* b,char* ans){
freopen("ans.tmp","w",stderr);
for(int i=0;i<m;i++) if(b[i]=='?') ans[i]='0';else ans[i]=b[i];
debug("%sn",a);
fclose(stderr);
}
void decoder(int n,int m,const char* a,char* ans){
freopen("ans.tmp","r",stdin);
scanf("%s",ans);
fclose(stdin);
}
``````
Code
``````#include "password.h"
char str[1010];
void encoder(int n,int m,int k,const char* a,const char* b,char* ans){for(int i=0;i<m;i++) if(b[i]=='?') ans[i]='0';else ans[i]=b[i];for(int i=0;i<n;i++) str[i]=a[i];}
void decoder(int n,int m,const char* a,char* ans){for(int i=0;i<n;i++) ans[i]=str[i];}
``````