比赛 |
4043级2023省选模拟赛7 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
Problem Setting |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
14.458 s |
代码语言 |
C++ |
内存使用 |
14.85 MiB |
提交时间 |
2023-03-29 11:05:02 |
显示代码纯文本
#include <bits/stdc++.h>
const int M = 1 << 20;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int maxm = 25;
char s[maxm][maxn];
int n,m,S[maxn],sum[M],f[M];
void add(int& x,int y) {
x += y;
if(x >= mod)
x -= mod;
return ;
}
int main() {
freopen("wentiji.in","r",stdin);
freopen("wentiji.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 0;i < m;++ i) {
scanf("%s",s[i] + 1);
for(int j = 1;j <= n;++ j)
S[j] |= (s[i][j] == 'H') << i;
}
for(int i = 1;i <= n;++ i)
++ sum[S[i]];
int ans = 0;
for(int i = 0;i < (1 << m);++ i) {
if(!sum[i])
continue ;
int now = 1,p = 0;
for(int k = sum[i];k;-- k) {
now = 1ll * now * k % mod;
add(p , now);
}
if(i == 0) {
add(ans , f[0] = p);
continue ;
}
f[i] = 1;
for(int j = (i - 1) & i;;j = (j - 1) & i) {
add(f[i] , f[j]);
if(j <= 0)
break ;
}
f[i] = 1ll * f[i] * p % mod;
add(ans , f[i]);
}
printf("%d\n",ans);
return 0;
}