这场出题人好像特别喜欢998244353，每个题里都放一个
A.Find Divisible
考察选手对输入输出的掌握
输出l 2*l即可(为啥你要放这个题，凑字数吗
#include<cstdio>
int n,l,r;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&l,&r);
printf("%d %d\n",l,*l);
}
return ;
}
B.Substring Removal
一道讨论题
首先，特别的，如果整个串由一种字母组成，答案为非空子串数目(即$len^2-1$)
首先我们找出来左右两边相同的最长连续的段，记左边段长为l，右边段长为r。
然后显然我们可以有l+r种删法，即左/右剩下1,2,3......l/r个字母
如果左右两段的字母相同，那么删掉中间+两边延伸又有l*r种删法
还有删整个串也是一种
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,mod=;
char a[N]; int len,lp,rp;
int main()
{
scanf("%d%s",&len,a+);
for(int i=;i<=len;i++)
if(a[i]!=a[i+]) {lp=i; break;}
for(int i=len;i;i--)
if(a[i]!=a[i-]) {rp=i; break;}
if(lp==len) printf("%lld",(1ll*len*len-)%mod);
else
{
long long ans=;
ans+=len-rp+,ans+=lp;
if(a[lp]==a[rp]) ans+=1ll*(lp)*(len-rp+);
printf("%lld",ans%mod);
}
return ;
}
C.Polygon for the Angle
一道小学数学题，题解居然还用了圆周角+圆心角，太浪费了
发现360的约数总共也没几个，于是预先筛一波内角为整数的正多边形。每次从小到大枚举，如果内角可以被$n-2$等分且内角大于询问的角就讨论一下。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rec[],n,rd,cnt,ans;
void Prework()
{
for(int i=;i*i<=;i++)
if(%i==) rec[++cnt]=i,rec[++cnt]=/i;
rec[++cnt]=,rec[++cnt]=,sort(rec+,rec++cnt);
}
int main()
{
Prework();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&rd),ans=-;
for(int j=;j<=cnt;j++)
{
int ra=-/rec[j];
if(ra==rd) {ans=rec[j]; break;}
else if(ra%(rec[j]-)==&&rd<=ra)
{
int ori=ra/(rec[j]-);
if(rd%ori==) {ans=rec[j]; break;}
}
}
printf("%d\n",ans);
}
return ;
}
D.Easy Problem
一道智商题
$dp[i][j]$表示到$i$位置已经拼出来了"hard"的前j个字符，讨论每个h,a,r,d的位置扔不扔即可，滚动数组可以滚成四个变量
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
long long n,cst,dp[]; char str[N];
int main()
{
scanf("%lld%s",&n,str+);
for(int i=;i<=n;i++)
{
scanf("%lld",&cst);
if(str[i]=='h') dp[]+=cst;
if(str[i]=='a') dp[]=min(dp[],dp[]+cst);
if(str[i]=='r') dp[]=min(dp[],dp[]+cst);
if(str[i]=='d') dp[]=min(dp[],dp[]+cst);
}
for(int i=;i<=;i++) dp[]=min(dp[],dp[i]);
printf("%lld",dp[]);
return ;
}
E.The Top Scorer
大力计数题，本场最难一题
整体思路是规定Hasan的得分(不严格)最高的情况下，枚举Hasan的得分，然后枚举得这个分的人数来计算
具体实现是这样的
$\huge ans=\frac{\sum\limits_{i=r}^s\sum\limits_{j=1}^p\frac{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}-\sum\limits_{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$让这些人不合法，剩下的插板
注意可能会出现组合数是负数但是也是有实际意义的情况，判掉(淦
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,mod=;
int p,s,r,ans,fac[N],inv[N];
void exGCD(int a,int b,int &x,int &y)
{
if(!b) {x=,y=; return;}
exGCD(b,a%b,y,x),y-=a/b*x;
}
int Inv(int x)
{
int xx,yy;
exGCD(x,mod,xx,yy);
return (xx%mod+mod)%mod;
}
void Prework()
{
fac[]=inv[]=;
for(int i=;i<=;i++) fac[i]=1ll*fac[i-]*i%mod;
inv[]=Inv(fac[]);
for(int i=;i;i--) inv[i]=1ll*inv[i+]*(i+)%mod;
}
int C(int n,int m)
{
if(n==m) return ; if(n<m) return ;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int Calc(int cnt,int lim,int tot)//计算：cnt个人，总分为tot，最高分小于lim的方案数
{
int ret=C(tot+cnt-,cnt-);//插板法
for(int i=,j;i<=cnt;i++,ret%=mod)//容斥：减掉1个的，加上2个的，减掉3个的......
j=i%?mod-:,ret+=1ll*j*C(cnt,i)%mod*C(tot-i*lim+cnt-,cnt-)%mod;//把i个lim分出去，强行让i个人超过限制
return (ret+mod)%mod;
}
int main()
{
scanf("%d%d%d",&p,&s,&r),Prework();
//思路：在规定Hasan得分(不严格)最高的情况下，枚举Hasan的得分，然后枚举得这个分的人数来计算
for(int i=r;i<=s;i++)//枚举Hasan的得分
for(int j=;j<=p&&i*j<=s;j++,ans%=mod)//枚举得这个分的人数
ans+=1ll*C(p-,j-)*Inv(j)%mod*Calc(p-j,i,s-i*j)%mod;//依次是选那j-1个人的方案数，在这些人里Hasan获胜的几率，还有上面写的那个东西
printf("%lld",1ll*ans*Inv(C(s-r+p-,p-))%mod);//总方案数
return ;
}
F.Inversion Expectation
又是一道分类讨论题(算吗？
设有$unk$个位置未知
已知-已知 求逆序对 ：树状数组入门题
未知-未知 求逆序对：总共$\frac{unk*(unk-1)}{2}$个有序对，其中$\frac{1}{2}$是逆序对，乘起来就好了
已知-未知 求逆序对：首先对每个数$i$预处理出$un[i]$有多少个小于$i$的数没出现。从右往左扫一遍，这样如果到一个数它后面有$unk'$个未知位置，那么每个位置都有$\frac{un[i]}{unk}$的几率形成一个逆序对，于是可以统计。反过来同理
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,mod=;
int num[N],pos[N],bit[N],unk[N];
int n,rd,cnt,ict,ans,luk,ruk;
void exGCD(int a,int b,int &x,int &y)
{
if(!b) {x=,y=; return;}
exGCD(b,a%b,y,x),y-=a/b*x;
}
int Qpow(int x,int k)
{
if(!k) return ;
if(k==) return x;
int tmp=Qpow(x,k/);
return k%?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
int Inv(int x)
{
int xx,yy;
exGCD(x,mod,xx,yy);
return (xx%mod+mod)%mod;
}
void Add(int x)
{
while(x<=n)
bit[x]++,x+=x&-x;
}
int Ask(int x)
{
int ret=;
while(x)
ret+=bit[x],x-=x&-x;
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&rd),num[i]=rd;
if(~rd)
{
ans+=Ask(n-rd+),ans%=mod;
pos[rd]=i,Add(n-rd+);
}
}
for(int i=;i<=n;i++)
unk[i]=cnt,cnt+=!pos[i]; ict=Inv(cnt);
ans+=1ll*cnt*(cnt-)%mod*Inv()%mod,ans%=mod;
for(int i=;i<=n;i++)
~num[i]?ans+=1ll*luk*(cnt-unk[num[i]])%mod*ict%mod,ans%=mod:luk++;
for(int i=n;i;i--)
~num[i]?ans+=1ll*ruk*unk[num[i]]%mod*ict%mod,ans%=mod:ruk++;
printf("%d",ans);
return ;
}
G.Lucky Tickets
这其实是前后都选$n$个数，问你相等的方案数$n$，用多项式乘法优化这个背包的过程即可。具体来说就是DFT之后自乘$\frac{n}{2}$次然后卷回去，最后每个位置平方就是和为这个的方案。注意因为要自乘好多次需要开够多项式的空间
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,mod=;
int n,ni,G,Gi,k,m,rd,ans;
int a[*N],rev[*N];
void exGCD(int a,int b,int &x,int &y)
{
if(!b) {x=,y=; return;}
exGCD(b,a%b,y,x),y-=a/b*x;
}
int Qpow(int x,int k)
{
if(!k) return ;
if(k==) return x;
int tmp=Qpow(x,k/);
return k%?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
int Inv(int x)
{
int xx,yy;
exGCD(x,mod,xx,yy);
return (xx%mod+mod)%mod;
}
void NTT(int *arr,int len,int typ)
{
for(int i=;i<=len;i++)
if(rev[i]>i) swap(arr[rev[i]],arr[i]);
for(int i=;i<=len;i<<=)
{
int lth=i>>,ort=Qpow(~typ?G:Gi,(mod-)/i);
for(int j=;j<len;j+=i)
{
int ori=,tmp;
for(int k=j;k<j+lth;k++,ori=1ll*ori*ort%mod)
{
tmp=1ll*ori*arr[k+lth]%mod;
arr[k+lth]=(arr[k]-tmp+mod)%mod;
arr[k]=(arr[k]+tmp)%mod;
}
}
}
if(typ==-)
{
int ni=Inv(len);
for(int i=;i<=len;i++)
arr[i]=1ll*arr[i]*ni%mod;
}
}
void Init()
{
scanf("%d%d",&n,&k);
G=,Gi=Inv(G),m=;
for(int i=;i<=k;i++)
scanf("%d",&rd),a[rd]++;
while(m<=n*) m<<=;
for(int i=;i<=m;i++)
rev[i]=(rev[i>>]>>)+(i&)*(m>>);
}
int main()
{
Init();
NTT(a,m,);
for(int i=;i<=m;i++) a[i]=Qpow(a[i],n/);
NTT(a,m,-);
for(int i=;i<=m;i++) ans+=1ll*a[i]*a[i]%mod,ans%=mod;
printf("%d",ans);
return ;
}