把赛中没有过的题争取补一下
题目链接：https://codeforces.com/gym/103861
C：
其实，最后每一种字符只有两种状态：
1.出现了x，此时就已经知道该字符有多少个了
2.没有出现x，那么相当于知道了这个字符至少有多少个记为\(L_I\)
同时，我们可以维护出每一个位置不可以填某个字符
考虑从左往右填，记录一个状态为填了前i个字符
由于有下界的限制，因此还需要每种字符已经出现了多少次
由于\(\sum L_i\le k\)，因此可以简单地压成一个二进制数
至于具体出现了多少次的字符，只需要保证再出现够\(L_i\)个字符后不再转移即可
目前的写法是O(\(262^kk\))的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
const int N=10005;
const int K=20;
int add (int x,int y){x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y){return (LL)x*y%MOD;}
int dec (int x,int y){x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
int t=1;
while (y)
{
if (y&1) t=mul(t,x);
y>>=1;x=mul(x,x);
}
return t;
}
int L[30],R[30];
char s[K],t[K];
int n,m;
int cnt[30];
bool ban[K][30];
bool p[N];
void Init()
{
scanf("%s%s",s,t);
for (int u=0;u<26;u++) cnt[u]=0;
for (int u=0;u<m;u++) if (t[u]=='O')
{
int x=s[u]-'A';
cnt[x]++;
for (int i=0;i<26;i++) if (i!=x) ban[u][i]=1;
}
for (int u=0;u<m;u++) if (t[u]!='O')
{
int x=s[u]-'A';
ban[u][x]=1;
if (t[u]=='-') cnt[x]++;
else {p[x]=false;R[x]=min(R[x],cnt[x]);}
}
for (int u=0;u<26;u++) L[u]=max(L[u],cnt[u]);
}
int mask[30];
int bel[30];
int f[K][1<<K];
int inv[30];
int main()
{
inv[0]=1;for (int u=1;u<=20;u++) inv[u]=mul(inv[u-1],Pow(u,MOD-2));
memset(ban,false,sizeof(ban));
for (int u=0;u<26;u++) p[u]=true;
scanf("%d%d",&n,&m);
for (int u=0;u<26;u++) {L[u]=0;R[u]=m;}
while (n--) Init();
for (int u=0;u<26;u++) if (L[u]>R[u]) {printf("0\n");return 0;}
n=0;
for (int u=0;u<26;u++)
{
mask[u]=0;
for (int i=0;i<L[u];i++)
{
mask[u]|=(1<<n);bel[n]=u;n++;
if (n>m) {printf("0\n");return 0;}
}
}
f[0][0]=1;
for (int u=0;u<m;u++)
for (int i=0;i<(1<<n);i++)
{
if (!f[u][i]) continue;
for (int k=0;k<n;k++) if (!ban[u][bel[k]]&&!((i>>k)&1))
{
f[u+1][i|(1<<k)]=add(f[u+1][i|(1<<k)],f[u][i]);
}
for (int k=0;k<26;k++) if (p[k]&&(mask[k]==(mask[k]&i))&&!ban[u][k])
{
f[u+1][i]=add(f[u+1][i],f[u][i]);
}
}
int ans=f[m][(1<<n)-1];
for (int u=0;u<26;u++) ans=mul(ans,inv[L[u]]);
printf("%d\n",ans);
return 0;
}