Codeforces Educational Round 57

这场出题人好像特别喜欢998244353，每个题里都放一个

A.Find Divisible

考察选手对输入输出的掌握

 1 #include<cstdio>
 2 int n,l,r;
 3 int main()
 4 {
 5     scanf("%d",&n);
 6     for(int i=1;i<=n;i++)
 7     {
 8         scanf("%d%d",&l,&r);
 9         printf("%d %d
",l,2*l);
10     }
11     return 0;
12 }

View Code

B.Substring Removal

一道讨论题

首先，特别的，如果整个串由一种字母组成，答案为非空子串数目(即$len^2-1$)

首先我们找出来左右两边相同的最长连续的段，记左边段长为l，右边段长为r。

然后显然我们可以有l+r种删法，即左/右剩下1,2,3......l/r个字母

如果左右两段的字母相同，那么删掉中间+两边延伸又有l*r种删法

还有删整个串也是一种

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=200005,mod=998244353;
 6 char a[N]; int len,lp,rp;
 7 int main()
 8 {
 9     scanf("%d%s",&len,a+1);
10     for(int i=1;i<=len;i++) 
11         if(a[i]!=a[i+1]) {lp=i; break;}
12     for(int i=len;i;i--) 
13         if(a[i]!=a[i-1]) {rp=i; break;}
14     if(lp==len) printf("%lld",(1ll*len*len-1)%mod);
15     else
16     {
17         long long ans=1;
18         ans+=len-rp+1,ans+=lp;
19         if(a[lp]==a[rp]) ans+=1ll*(lp)*(len-rp+1);
20         printf("%lld",ans%mod);
21     }
22     return 0;
23 }

View Code

C.Polygon for the Angle

一道小学数学题，题解居然还用了圆周角+圆心角，太浪费了

发现360的约数总共也没几个，于是预先筛一波内角为整数的正多边形。每次从小到大枚举，如果内角可以被$n-2$等分且内角大于询问的角就讨论一下。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int rec[360],n,rd,cnt,ans;
 6 void Prework()
 7 {
 8     for(int i=3;i*i<=360;i++)
 9         if(360%i==0) rec[++cnt]=i,rec[++cnt]=360/i;
10     rec[++cnt]=180,rec[++cnt]=360,sort(rec+1,rec+1+cnt);
11 }
12 int main()
13 {
14     Prework();
15     scanf("%d",&n);
16     for(int i=1;i<=n;i++)
17     {
18         scanf("%d",&rd),ans=-1;
19         for(int j=1;j<=cnt;j++)
20         {
21             int ra=180-360/rec[j];
22             if(ra==rd) {ans=rec[j]; break;}
23             else if(ra%(rec[j]-2)==0&&rd<=ra)
24             {
25                 int ori=ra/(rec[j]-2);
26                 if(rd%ori==0) {ans=rec[j]; break;}
27             }
28         }
29         printf("%d
",ans);
30     }
31     return 0;
32 }

View Code

D.Easy Problem

一道智商题

$dp[i][j]$表示到$i$位置已经拼出来了"hard"的前j个字符，讨论每个h,a,r,d的位置扔不扔即可，滚动数组可以滚成四个变量

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=100005;
 6 long long n,cst,dp[4]; char str[N];
 7 int main()
 8 {
 9     scanf("%lld%s",&n,str+1);
10     for(int i=1;i<=n;i++)
11     {
12         scanf("%lld",&cst);
13         if(str[i]=='h') dp[0]+=cst;
14         if(str[i]=='a') dp[1]=min(dp[0],dp[1]+cst);
15         if(str[i]=='r') dp[2]=min(dp[1],dp[2]+cst);
16         if(str[i]=='d') dp[3]=min(dp[2],dp[3]+cst);
17     }
18     for(int i=1;i<=3;i++) dp[0]=min(dp[0],dp[i]);
19     printf("%lld",dp[0]);
20     return 0;
21 }

View Code

E.The Top Scorer

大力计数题，本场最难一题

整体思路是规定Hasan的得分(不严格)最高的情况下，枚举Hasan的得分，然后枚举得这个分的人数来计算

具体实现是这样的

$huge ans=frac{sumlimits_{i=r}^ssumlimits_{j=1}^pfrac{1}{j}C_{p-1}^{j-1}Calc(p-j,s-i*j,i)}{C_{s-r+p-1}^{p-1}}$

解释一下这是在干啥：底下的是总方案数，插板法；上面是先枚举Hasan的得分$i$，然后枚举得这个分的人数$j$，这样Hasan有$frac{1}{j}$的概率获胜，然后从除了Hasan的$p-1$个人里选这$j$个人有$C_{p-1}{j-1}$种方案。后面那个$Calc(x,y,z)$表示计算有$x$个人总分为$y$最高分小于$z$的方案数

那么有

$huge Calc(x,y,z)=C_{y+x-1}^{x-1}-sumlimits_{i=1}^{x}(-1)^iC_{x}^{i}C_{y-i*z+x-1}^{x-1}$

再解释一下：这是在容斥，容斥系数就不说了，$C_{x}^{i}$是规定选出$i$个人去不满足方案的方案数，$C_{y-i*z+x-1}^{x-1}$是先留出$i$个$z$让这些人不合法，剩下的插板

注意可能会出现组合数是负数但是也是有实际意义的情况，判掉(淦

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=5500,mod=998244353;
 6 int p,s,r,ans,fac[N],inv[N];
 7 void exGCD(int a,int b,int &x,int &y)
 8 {
 9     if(!b) {x=1,y=0; return;}
10     exGCD(b,a%b,y,x),y-=a/b*x;
11 }
12 int Inv(int x)
13 {
14     int xx,yy;
15     exGCD(x,mod,xx,yy);
16     return (xx%mod+mod)%mod;
17 }
18 void Prework()
19 {
20     fac[0]=inv[0]=1;
21     for(int i=1;i<=5200;i++) fac[i]=1ll*fac[i-1]*i%mod;
22     inv[5200]=Inv(fac[5200]);
23     for(int i=5199;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
24 }
25 int C(int n,int m)
26 {
27     if(n==m) return 1; if(n<m) return 0;
28     return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
29 }
30 int Calc(int cnt,int lim,int tot)//计算：cnt个人，总分为tot，最高分小于lim的方案数 
31 {
32     int ret=C(tot+cnt-1,cnt-1);//插板法 
33     for(int i=1,j;i<=cnt;i++,ret%=mod)//容斥：减掉1个的，加上2个的，减掉3个的...... 
34         j=i%2?mod-1:1,ret+=1ll*j*C(cnt,i)%mod*C(tot-i*lim+cnt-1,cnt-1)%mod;//把i个lim分出去，强行让i个人超过限制
35     return (ret+mod)%mod; 
36 }
37 int main()
38 {
39     scanf("%d%d%d",&p,&s,&r),Prework();
40     //思路：在规定Hasan得分(不严格)最高的情况下，枚举Hasan的得分，然后枚举得这个分的人数来计算 
41     for(int i=r;i<=s;i++)//枚举Hasan的得分 
42         for(int j=1;j<=p&&i*j<=s;j++,ans%=mod)//枚举得这个分的人数 
43             ans+=1ll*C(p-1,j-1)*Inv(j)%mod*Calc(p-j,i,s-i*j)%mod;//依次是选那j-1个人的方案数，在这些人里Hasan获胜的几率，还有上面写的那个东西
44     printf("%lld",1ll*ans*Inv(C(s-r+p-1,p-1))%mod);//总方案数 
45     return 0;
46 }

View Code

F.Inversion Expectation

又是一道分类讨论题(算吗？

设有$unk$个位置未知

已知-已知求逆序对：树状数组入门题

未知-未知求逆序对：总共$frac{unk*(unk-1)}{2}$个有序对，其中$frac{1}{2}$是逆序对，乘起来就好了

已知-未知求逆序对：首先对每个数$i$预处理出$un[i]$有多少个小于$i$的数没出现。从右往左扫一遍，这样如果到一个数它后面有$unk'$个未知位置，那么每个位置都有$frac{un[i]}{unk}$的几率形成一个逆序对，于是可以统计。反过来同理

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=200005,mod=998244353;
 6 int num[N],pos[N],bit[N],unk[N];
 7 int n,rd,cnt,ict,ans,luk,ruk;
 8 void exGCD(int a,int b,int &x,int &y)
 9 {
10     if(!b) {x=1,y=0; return;}
11     exGCD(b,a%b,y,x),y-=a/b*x;
12 }
13 int Qpow(int x,int k)
14 {
15     if(!k) return 1;
16     if(k==1) return x;
17     int tmp=Qpow(x,k/2);
18     return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
19 }
20 int Inv(int x)
21 {
22     int xx,yy;
23     exGCD(x,mod,xx,yy);
24     return (xx%mod+mod)%mod;
25 }
26 void Add(int x)
27 {
28     while(x<=n)
29         bit[x]++,x+=x&-x;
30 }
31 int Ask(int x)
32 {
33     int ret=0;
34     while(x)
35         ret+=bit[x],x-=x&-x;
36     return ret;
37 }
38 int main()
39 {
40     scanf("%d",&n);
41     for(int i=1;i<=n;i++)
42     {
43         scanf("%d",&rd),num[i]=rd;
44         if(~rd) 
45         {
46             ans+=Ask(n-rd+1),ans%=mod;
47             pos[rd]=i,Add(n-rd+1);
48         }
49     }
50     for(int i=1;i<=n;i++)
51         unk[i]=cnt,cnt+=!pos[i]; ict=Inv(cnt);
52     ans+=1ll*cnt*(cnt-1)%mod*Inv(4)%mod,ans%=mod;
53     for(int i=1;i<=n;i++)
54         ~num[i]?ans+=1ll*luk*(cnt-unk[num[i]])%mod*ict%mod,ans%=mod:luk++;
55     for(int i=n;i;i--)
56         ~num[i]?ans+=1ll*ruk*unk[num[i]]%mod*ict%mod,ans%=mod:ruk++;
57     printf("%d",ans);
58     return 0;
59 }

View Code

G.Lucky Tickets

这其实是前后都选$n$个数，问你相等的方案数$n$，用多项式乘法优化这个背包的过程即可。具体来说就是DFT之后自乘$frac{n}{2}$次然后卷回去，最后每个位置平方就是和为这个的方案。注意因为要自乘好多次需要开够多项式的空间

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1000005,mod=998244353;
 6 int n,ni,G,Gi,k,m,rd,ans;
 7 int a[4*N],rev[4*N];
 8 void exGCD(int a,int b,int &x,int &y)
 9 {
10     if(!b) {x=1,y=0; return;}
11     exGCD(b,a%b,y,x),y-=a/b*x;
12 }
13 int Qpow(int x,int k)
14 {
15     if(!k) return 1;
16     if(k==1) return x;
17     int tmp=Qpow(x,k/2);
18     return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
19 }
20 int Inv(int x)
21 {
22     int xx,yy;
23     exGCD(x,mod,xx,yy);
24     return (xx%mod+mod)%mod;
25 }
26 void NTT(int *arr,int len,int typ)
27 {
28     for(int i=0;i<=len;i++)
29         if(rev[i]>i) swap(arr[rev[i]],arr[i]);
30     for(int i=2;i<=len;i<<=1)
31     {
32         int lth=i>>1,ort=Qpow(~typ?G:Gi,(mod-1)/i);
33         for(int j=0;j<len;j+=i)
34         {
35             int ori=1,tmp;
36             for(int k=j;k<j+lth;k++,ori=1ll*ori*ort%mod)
37             {
38                 tmp=1ll*ori*arr[k+lth]%mod;
39                 arr[k+lth]=(arr[k]-tmp+mod)%mod;
40                 arr[k]=(arr[k]+tmp)%mod;
41             }
42         }
43     }
44     if(typ==-1)
45     {
46         int ni=Inv(len);
47         for(int i=0;i<=len;i++)
48             arr[i]=1ll*arr[i]*ni%mod;
49     }
50 }
51 void Init()
52 {
53     scanf("%d%d",&n,&k);
54     G=3,Gi=Inv(G),m=1;
55     for(int i=1;i<=k;i++)
56         scanf("%d",&rd),a[rd]++;
57     while(m<=n*5) m<<=1;
58     for(int i=1;i<=m;i++)
59         rev[i]=(rev[i>>1]>>1)+(i&1)*(m>>1);
60 }
61 int main()
62 {
63     Init();
64     NTT(a,m,1);
65     for(int i=0;i<=m;i++) a[i]=Qpow(a[i],n/2);
66     NTT(a,m,-1);
67     for(int i=0;i<=m;i++) ans+=1ll*a[i]*a[i]%mod,ans%=mod;
68     printf("%d",ans);
69     return 0;
70 }

View Code