A. Emotional Flutter
直接将所有黑块平移到 \([1-k,0]\) 的区间即可，然后找有没有没被覆盖过的整点
注意特判 \(1-k\) 以及 \(0\) 的可行性，考场这里写挂成 \(10\) 分
B. Medium Counting
设 \(f[i][j][pos][c]\) 表示第 \(i\) 个到第 \(j\) 个字符串考虑从 \(pos\) 开始的后缀，且第 \(pos\) 位至少填 \(c\) 的方案数
\(f[i][j][pos][c]+=f[i][j][pos][c+1]\)
\(f[i][j][pos][c]+=f[i][k][pos+1][0] * f[k+1][j][pos][c+1]\)
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=55;
char c[maxn][maxn];
int a[maxn][maxn],len,n,f[maxn][maxn][maxn][30];
const int mod=990804011;
int dfs(int l,int r,int pos,int c){
if(l>r)return 1;
if(pos==len+1)return l==r;
if(c>26)return 0;
if(~f[l][r][pos][c])return f[l][r][pos][c];
int ans=0;
ans+=dfs(l,r,pos,c+1);
for(int i=l;i<=r;i++){
// if(!(a[i][pos]==c||(a[i][pos]==27&&c)))break;
if(a[i][pos]!=c&&!(a[i][pos]==27&&c))break;
ans+=dfs(l,i,pos+1,0)*dfs(i+1,r,pos,c+1)%mod;
ans%=mod;
}
f[l][r][pos][c]=ans;
return ans;
}
signed main(){
memset(f,-1,sizeof f);
cin>>n;
for(int i=1;i<=n;i++){
scanf("%s",c[i]+1);
int l=strlen(c[i]+1);
len=max(len,l);
for(int j=1;j<=l;j++){
if(c[i][j]!='?')a[i][j]=c[i][j]-'a'+1;
else a[i][j]=27;
}
}
cout<<dfs(1,n,1,0);
return 0;
}
C. Huge Counting
由于只有 \(f(1,1,……,1)\) 有贡献，所以相当于是每个点的值是走到这个点的方案数
是多重集排列：
然而答案只问奇偶，所以只要统计分子分母 \(2\) 的因子数是否相等即可
转化成下面的式子：
\[\sum_{w=2^i} (\frac{\sum x_i}{w}-\sum \frac{x_i}{w}) \]