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)\) 有贡献，所以相当于是每个点的值是走到这个点的方案数
是多重集排列：
\[\frac{(\sum x_i)!}{\prod x_i!}
\]
然而答案只问奇偶，所以只要统计分子分母 \(2\) 的因子数是否相等即可
转化成下面的式子：
\[\sum_{w=2^i} (\frac{\sum x_i}{w}-\sum \frac{x_i}{w})
\]
发现 \(x\) 每一位如果有进位一定在相减时产生差值
所以约束条件就是所有 \(x\) 每一位最多一个为 \(1\)，数位 \(dp\) 即可
数位 \(dp\) 的结果是形如小于等于 \(lim_i\) 的方案数，发现还有下边界，容斥即可
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=990804011;
const int up=50;
const int maxn=105,maxm=1005;
int f[maxn][maxm],ans,n,l[maxn],r[maxn],all,lim[maxn],t;
bool flag;
int dp(){
memset(f,0,sizeof f);
all=(1<<n)-1;
f[up][all]=1;
// if(!flag){
// for(int i=1;i<=n;i++)cout<<lim[i]<<" ";
// cout<<endl<<endl;
// }
for(int i=up;i>=1;i--){
for(int S=0;S<=all;S++){
if(f[i][S]){
// if(!flag)cout<<i<<" "<<S<<" "<<f[i][S]<<endl;
int T=0;
// for(int j=0;j<n;j++){
// if(S>>j&1 && !(limit[j+1]>>i-1&1))
// }
for(int j=1;j<=n;j++){
if( ((1<<(j-1))&S) && (!((1ll<<(i-1))&lim[j])) ){
T|=(1<<(j-1));
}
}
f[i-1][T]=(f[i-1][T]+f[i][S])%mod;
// if(!flag)cout<<"ppp "<<T<<endl;
for(int j=1;j<=n;j++){
if( (1<<(j-1))&S && (1ll<<(i-1))&lim[j] || (!((1<<(j-1))&S)) ){
//int TT=T&((-1)^1<<(j-1)) | (((1<<(j-1))&S && (1ll<<(i-1))&lim[j])?1<<(j-1):0);
int TT;
if((1<<(j-1))&S)TT=T|(1<<(j-1));
else TT=T&((-1)^1<<(j-1));
f[i-1][TT]=(f[i-1][TT]+f[i][S])%mod;
}
}
}
}
}
flag=true;
int res=0;
for(int i=0;i<=all;i++)res=(res+f[0][i])%mod;
return res;
}
void rc(int pos,int op){
if(pos==n+1){
// cout<<"hhh "<<dp()<<endl;
ans=(ans+dp()*op+mod)%mod;
return ;
}
lim[pos]=r[pos];
rc(pos+1,op);
if(l[pos]>=1){
lim[pos]=l[pos]-1;
rc(pos+1,-op);
}
return ;
}
signed main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++){
cin>>l[i]>>r[i];
l[i]--;
r[i]--;
}
ans=0;
rc(1,1);
cout<<ans<<endl;
}
return 0;
}
D. 字符消除2
容易发现可行循环长度是 \(kmp\) 一直取 \(nxt\) 的结果
那么构造 \(01\) 串的时候，如果 \(nxt[nxt[i]] * 2>nxt[i]\)，直接把不重复的后缀复制过去即可
否则整个复制后中间还有空隙，按照贪心的思想全填 \(0\) 最优，但是可能会出现更多的循环节，那么暴力 \(kmp\) 这一区间的 \(01\) 串，如果有不满足的位置，把中间部分最后一个 \(0\) 改成 \(1\)，这样一定破坏了原来多出来的匹配部分而满足条件
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
char a[maxn];
int nxt[maxn],nxt1[maxn],t,n,cnt,p[maxn];
bool ans[maxn];
void kmp(){
memset(nxt,0,sizeof nxt);
for(int i=2,j=0;i<=n;i++){
while(j&&a[i]!=a[j+1])j=nxt[j];
if(a[i]==a[j+1])j++;
nxt[i]=j;
}
cnt=0;
p[++cnt]=n;
int x=nxt[n];
while(x){
p[++cnt]=x;
x=nxt[x];
}
return ;
}
void kmp1(int n){
memset(nxt1,0,sizeof nxt1);
for(int i=2,j=0;i<=n;i++){
while(j&&ans[i]!=ans[j+1])j=nxt1[j];
if(ans[i]==ans[j+1])j++;
nxt1[i]=j;
}
return ;
}
int main(){
cin>>t;
while(t--){
memset(ans,0,sizeof ans);
scanf("%s",a+1);
n=strlen(a+1);
kmp();
reverse(p+1,p+cnt+1);
// for(int i=1;i<=cnt;i++)cout<<p[i]<<" ";
// cout<<endl;
if(p[1]>1)ans[p[1]]=1;
for(int i=2;i<=cnt;i++){
if(p[i-1]*2>=p[i]){
int len=p[i]-p[i-1];
for(int j=p[i];j>=p[i-1]+1;j--)ans[j]=ans[j-len];
}
else{
int len=p[i]-p[i-1];
for(int j=p[i];j>=p[i]-p[i-1]+1;j--)ans[j]=ans[j-len];
kmp1(p[i]);
// for(int j=1;j<=n;j++)cout<<ans[j];
// cout<<endl;
for(int j=1;j<=i;j++){
// cout<<nxt1[j]<<" ";
if(nxt1[p[j]]!=nxt[p[j]]){
ans[p[i]-p[i-1]]=1;
break;
}
}
// cout<<endl;
}
}
for(int i=1;i<=n;i++)cout<<ans[i];
cout<<endl;
}
return 0;
}