好久没写一整场 CF 或者 AT 的题解了，所以写一篇。
C
有点意思的题。
考虑先放横再放竖，若确定所有横的位置，那么每列独立。所以记 \(f_i\) 表示第 \(i\) 列最多放多少个，考虑放一个横对 \(f_i\) 的影响。
若 \(n\) 为奇数，那么第一行放满显然最优。若某时 \(A>1\)，那么放一个 \(2\times 2\) 的形式一定最优。
现在有可能还剩下一个。记此时第一个可以放的位置为 \((x,y)\)，若直接放这会使 \(f_y,f_{y+1}\) 均减一；而当 \(n,m\) 均为奇数的时候，放 \((x+1,m-1)\) 则会只让 \(f_m\) 减一。
那就做完了，复杂度 \(O(nm)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 1010
int n,m,sa,sb;
char ans[N][N];
main()
{
scanf("%d%d%d%d",&n,&m,&sa,&sb);
for(reg int i=1,j;i<=n;++i)for(j=1;j<=m;++j)ans[i][j]='.';
reg int x=1,y=1;
if(m==1)goto skip;
if(n&1)
{
while(y<m&&sa)--sa,ans[x][y]='<',ans[x][y+1]='>',y+=2;
++x,y=1;
}
while(x<n&&sa>1)
{
sa-=2,ans[x][y]=ans[x+1][y]='<';
ans[x][y+1]=ans[x+1][y+1]='>',y+=2;
if(y>=m)x+=2,y=1;
}
if(x<=n&&sa)--sa,ans[x+1][m-1]='<',ans[x+1][m]='>';
skip:;
if(sa)puts("NO"),exit(0);
for(reg int j=1,i;j<=m;++j)for(i=1;i<n&&sb;++i)
if(ans[i][j]=='.'&&ans[i+1][j]=='.')ans[i][j]='^',ans[i+1][j]='v',--sb;
if(sb)puts("NO"),exit(0);
puts("YES");
for(reg int i=1,j;i<=n;++i,puts(""))for(j=1;j<=m;++j)putchar(ans[i][j]);
}
D
感觉比 C 简单很多。
直接嗯 dp 不太好做到太低的复杂度，考虑观察一点性质。
容易发现并证明，对于给定字符串，它的贡献为最长回文子序列。
那就可以直接区间 dp。复杂度 \(O(n^2k)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 330
int n,k,f[N][N][N],ans;
char s[N];
IL void cmax(reg int &x,reg int y){x<y?x=y:0;}
main()
{
scanf("%s%d",s+1,&k),n=strlen(s+1);
for(reg int i=1,j;i<=n;++i)for(j=0;j<=k;++j)f[i][i][j]=-1,f[i][i+1][j]=0;
for(reg int l=n,r,i,w;l;--l)for(r=l;r<=n;++r)for(i=0;i<=k;++i)
{
w=f[l][r][i];
if(s[l]==s[r])cmax(ans,w+=2),cmax(f[l-1][r+1][i],w);
else
{
cmax(ans,w),cmax(f[l-1][r][i],w),cmax(f[l][r+1][i],w);
if(i<k)cmax(ans,w+=2),cmax(f[l-1][r+1][i+1],w);
}
}
printf("%d\n",ans);
}
E
简单题。
对于一只变色龙，考虑其为红色的充要条件。
若红色比蓝色多，显然成立；若红色与蓝色一样多，要求最后一个位置为蓝色。
回到原问题，枚举红色数量 \(i\)，则蓝色数量 \(j=k-i\)。
-
\(i\ge j+n\)，那么答案显然为 \(\binom{k}{i}\)。
-
\(i>j\)，会有 \(x=n-i+j\) 只变色龙蓝色与红色一样多。考虑他们最后一个蓝色的选取，显然选最后 \(x\) 个更优。这也就要求最后 \(x\) 个蓝色都能与前面的红色匹配，计数是经典的折线容斥。
-
\(i=j\)，所有变色龙蓝色与红色一样多，那就没有变色龙可以处理最后的一些红色。所以要求多了一个第 \(k\) 个球为蓝色，这也是折线容斥。
时间复杂度 \(O(k)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define mod 998244353
#define N 500500
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
int fac[N],ifac[N],inv[N];
IL void init(reg int n)
{
fac[0]=ifac[0]=inv[1]=1;
for(reg int i=2;i<=n;++i)inv[i]=Mul(mod-mod/i,inv[mod%i]);
for(reg int i=1;i<=n;++i)fac[i]=Mul(fac[i-1],i),ifac[i]=Mul(ifac[i-1],inv[i]);
}
IL int C(reg int n,reg int m){return n>=m&&m>=0?Mul(fac[n],Mul(ifac[m],ifac[n-m])):0;}
int n,m,ans;
main()
{
n=read(),m=read(),init(5e5);
for(reg int i=(m+1)/2,j;i<=m;++i)
{
j=m-i;
if(i-j>=n)Pls(ans,C(m,i));
else if(i>j)n<=i?Pls(ans,Sub(C(m,i),C(m,i+i-n+1))),0:0;
else n<=i?Pls(ans,Sub(C(m-1,i),C(m-1,i+i-n+1))),0:0;
}
printf("%d\n",ans);
}
F
没那么简单的简单题。
由于 A 影响的都是前缀，所以考虑逐列确定。
第 \(j\) 列放区间 \([b_j,c_j]\) 时，考虑第 \(i\) 行的影响。
-
\(a_i<j\)，可以任意作为端点。
-
\(a_i>j\)，不能作为端点。
-
\(a_i=j\)，\(i\in [b_j,c_j]\)。
注意到上述第二类事实上对答案没有影响，方案数事实上只需要将其他两类归并起来即可。
记 \(f_{i,j}\) 表示第 \(i\) 列时，有 \(j\) 个这两类的行。转移枚举第三类个数，系数通过区间包含的组合意义不难推导。
直接暴力 dp 为 \(O(n^2m)\)，但注意到所有转移都是卷积的形式，可以优化到 \(O(nm\log n)\)。
#include<bits/stdc++.h>
#define IL inline
#define reg register
#define mod 998244353
#define N 40040
IL int read()
{
reg int x=0; reg char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
IL int power(reg int x,reg int p){reg int r=1; for(;p;p>>=1,x=Mul(x,x))if(p&1)r=Mul(r,x); return r;}
int fac[N],ifac[N],inv[N];
IL void init(reg int n)
{
fac[0]=ifac[0]=inv[1]=1;
for(reg int i=2;i<=n;++i)inv[i]=Mul(mod-mod/i,inv[mod%i]);
for(reg int i=1;i<=n;++i)fac[i]=Mul(fac[i-1],i),ifac[i]=Mul(ifac[i-1],inv[i]);
}
int a[N],b[N],r[N],len,val[N+N];
IL void prework(reg int n)
{
for(len=1;len<=n;len<<=1);
for(reg int i=1;i<len;++i)r[i]=r[i>>1]+(i&1)*len>>1;
}
IL void dft(reg int *f)
{
for(reg int i=len;i--;)if(r[i]>i)std::swap(f[i],f[r[i]]);
for(reg int k=2,i,j,x,y;k<=len;k<<=1)for(i=0;i<len;i+=k)for(j=i;j<i+k/2;++j)
x=f[j],y=Mul(f[j+k/2],val[k+j-i]),f[j]=Add(x,y),f[j+k/2]=Sub(x,y);
}
IL void idft(reg int *f)
{
dft(f),std::reverse(f+1,f+len);
for(reg int i=len,inv=mod-(mod-1)/len;i--;)f[i]=Mul(f[i],inv);
}
int n,m,f[N],g[N],ans;
main()
{
n=read(),m=read(),init(n),f[0]=1;
for(reg int k=2,i,w;k<N;k<<=1)
{
w=power(3,(mod-1)/k),val[k]=1;
for(i=1;i<k/2;++i)val[k+i]=Mul(val[k+i-1],w);
}
prework(n+n);
for(reg int i=1,j;i<=m;++i)
{
for(j=0;j<=n;++j)
{
g[j]=Mul(j+1,f[j]);
if(j)Pls(g[j],Mul(j,f[j-1]));
}
memset(a,0,len<<2),memset(b,0,len<<2);
for(j=0;j<=n;++j)a[j]=Mul(f[j],j>1?ifac[j-2]:0),b[j]=ifac[j+2];
dft(a),dft(b);
for(j=len;j--;)a[j]=Mul(a[j],b[j]);
idft(a);
for(j=0;j<=n;++j)Pls(g[j],Mul(fac[j],a[j]));
memset(a,0,len<<2),memset(b,0,len<<2);
for(j=0;j<=n;++j)a[j]=Mul(f[j]*2,j?ifac[j-1]:0),b[j]=j?ifac[j+1]:0;
dft(a),dft(b);
for(j=len;j--;)a[j]=Mul(a[j],b[j]);
idft(a);
for(j=0;j<=n;++j)Pls(g[j],Mul(fac[j],a[j]));
memset(a,0,len<<2),memset(b,0,len<<2);
for(j=0;j<=n;++j)a[j]=Mul(f[j],ifac[j]),b[j]=j>1?ifac[j]:0;
dft(a),dft(b);
for(j=len;j--;)a[j]=Mul(a[j],b[j]);
idft(a);
for(j=0;j<=n;++j)Pls(g[j],Mul(fac[j],a[j])),f[j]=g[j],g[j]=0;
}
for(reg int i=0;i<=n;++i)Pls(ans,Mul(f[i],Mul(ifac[i],ifac[n-i])));
printf("%d\n",Mul(ans,fac[n]));
}