Codeforces Hello 2019

A.直接判。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=10;
10 char s[N][N];
11 
12 int main(){
13     rep(i,1,6) scanf("%s",s[i]);
14     rep(i,2,6) if (s[i][0]==s[1][0] || s[i][1]==s[1][1]) { puts("YES"); return 0; }
15     puts("NO");
16     return 0;
17 }

B.2^n枚举每次是顺时针还是逆时针，模拟。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=20;
10 int n,ss,a[N];
11 
12 int main(){
13     scanf("%d",&n); ss=(1<<n)-1;
14     rep(i,1,n) scanf("%d",&a[i]);
15     rep(S,0,ss){
16         int s=0;
17         rep(i,1,n) if (S&(1<<(i-1))) s=(s+a[i])%360; else s=(s-a[i]+360)%360;
18         if (!s){ puts("YES"); return 0; }
19     }
20     puts("NO");
21     return 0;
22 }

C.将所有串分成三类：只能作为左半段的串、只能作为右半段的串、两边都能做的串。可以发现，第三类串只能和第三类串匹配。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 5 using namespace std;
 6 
 7 const int N=500010;
 8 char s[N];
 9 int n,ans,b[N],c[N];
10 
11 int main(){
12     scanf("%d",&n);
13     rep(i,1,n){
14         scanf("%s",s+1);
15         int len=strlen(s+1),tot1=0,tot2=0,f1=1,f2=1;
16         rep(j,1,len){
17             if (s[j]=='(') tot1++; else tot2++;
18             if (tot2>tot1) f1=0;
19         }
20         tot1=tot2=0;
21         for (int j=len; j; j--){
22             if (s[j]=='(') tot1++; else tot2++;
23             if (tot1>tot2) f2=0;
24         }
25         if (f1 && f2) ans++;
26         else if (f1) b[tot1-tot2]++;
27             else if (f2) c[tot2-tot1]++;
28     }
29     ans>>=1;
30     rep(i,0,500000) ans+=min(b[i],c[i]);
31     printf("%d
",ans);
32     return 0;
33 }

D.发现这是一个积性函数，也就是可以对每个质因子做一遍DP，然后将结果乘起来。

 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 7 typedef long long ll;
 8 using namespace std;
 9 
10 const int N=30010,mod=1e9+7;
11 int tot,mx,b[N],c[N];
12 ll n,K,ans=1,a[N],inv[N],f[N][100];
13 
14 int main(){
15     cin>>n>>K; ll ed=sqrt(n),t=n;
16     inv[0]=inv[1]=1; rep(i,2,100) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
17     rep(i,2,ed) if (t%i==0){
18         a[++tot]=i;
19         while (t%i==0) t/=i,b[tot]++;
20         mx=max(mx,b[tot]);
21     }
22     if (t>1) a[++tot]=t,b[tot]=1;
23     rep(x,1,tot){
24         rep(i,0,K) rep(j,0,mx) f[i][j]=0;
25         f[0][b[x]]=1;
26         rep(i,1,K){
27             for (int j=b[x]; ~j; j--)
28                 rep(k,j,b[x]) f[i][j]=(f[i][j]+f[i-1][k]*inv[k+1])%mod;
29         }
30         ll res=0,s=1;
31         rep(i,0,b[x]) res=(res+f[K][i]*s)%mod,s=(s*a[x])%mod;
32         ans=ans*res%mod;
33     }
34     cout<<ans<<endl;
35     return 0;
36 }

F.先做一次莫比乌斯变换，回答询问的时候再反演回来。

具体来说，对每个集合用bitset维护f[i]表示i的倍数的个数的奇偶性。

操作一直接赋值。操作二就是异或。操作三发现只有两个集合中的f[i]都是奇数做笛卡尔积后才会是奇数，所以就是按位与。

操作四先预处理对每个询问x，x的哪些倍数会对答案产生贡献，然后直接按位与。

https://blog.csdn.net/Rose_max/article/details/85833951

 1 #include<bitset>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 using namespace std;
 7 
 8 const int N=7010,M=100010;
 9 int n,T,t,x,y,z,c[N];
10 bitset<N>p[N],q[N],a[M];
11 
12 int main(){
13     scanf("%d%d",&n,&T); c[1]=1;
14     rep(i,1,N-1) for (int j=i*2; j<N-1; j+=i) c[j]^=c[i];
15     rep(i,1,N-1) rep(j,1,N-1){
16         if (i%j==0) p[i][j]=1;
17         if (j%i==0) q[i][j]=c[j/i];
18     }
19     while (T--){
20         scanf("%d%d%d",&t,&x,&y);
21         if (t==1) a[x]=p[y];
22         else if (t==2) scanf("%d",&z),a[x]=a[y]^a[z];
23             else if (t==3) scanf("%d",&z),a[x]=a[y]&a[z];
24                 else cout<<((a[x]&q[y]).count()&1);
25     }
26     return 0;
27 }

G.先斯特林反演变成组合数，然后就是f[x][i]表示x子树内选i条边，X的方案数。DP具体看这里的代码注释。

 1 #include<cstdio>
 2 #include<iostream>
 3 #define rep(i,l,r) for (int i=(l);i<=(r);i++)
 4 #define ll long long
 5 
 6 using namespace std;
 7 
 8 const int N=1e5+10,M=210,mod=1e9+7;
 9 int n,k,x,y,cnt,h[N],sz[N],f[N][M],g[M],ans[M],S[M][M],fac[M],Ans;
10 struct edge{int to,nxt;}e[N<<1];
11 
12 void adde(int x,int y){
13     e[++cnt].to=y; e[cnt].nxt=h[x]; h[x]=cnt;
14 }
15 
16 inline void upd(int &x,int y){x+=y; x-=x>=mod?mod:0;}
17 
18 void dfs(int u,int par){
19     sz[u]=1; f[u][0]=2;
20     for (int i=h[u],v;i;i=e[i].nxt)
21         if ((v=e[i].to)!=par){
22             dfs(v,u);
23             rep(j,0,min(sz[u],k)) g[j]=f[u][j],f[u][j]=0;
24             rep(j,0,min(sz[u],k))
25                 rep(l,0,min(sz[v],k-j))
26                     upd(f[u][j+l],(ll)g[j]*f[v][l]%mod);
27             rep(j,0,min(sz[v],k)) upd(ans[j],mod-f[v][j]);
28             sz[u]+=sz[v];
29         }
30     rep(i,0,min(sz[u],k)) upd(ans[i],f[u][i]);
31     for (int i=min(sz[u],k);i;i--) upd(f[u][i],f[u][i-1]);
32     upd(f[u][1],mod-1);
33 }
34 
35 int main(){
36     scanf("%d%d",&n,&k);
37     rep(i,1,n-1) scanf("%d%d",&x,&y),adde(x,y),adde(y,x);
38     dfs(1,0); fac[0]=1;
39     rep(i,1,k) S[i][1]=1,fac[i]=(ll)fac[i-1]*i%mod;
40     rep(i,2,k) rep(j,1,i) S[i][j]=((ll)S[i-1][j]*j+S[i-1][j-1])%mod;
41     rep(i,0,k) upd(Ans,(ll)S[k][i]*fac[i]%mod*ans[i]%mod);
42     printf("%d
",Ans);
43     return 0;
44 }