比赛 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;
}