QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#103522 | #5658. Problem Setting | retcarizy | 100 ✓ | 137ms | 91024kb | C++14 | 1.3kb | 2023-05-06 14:31:48 | 2023-05-06 14:31:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
char s[N];
int n,m;
int f[N],sum[1<<20],fac[N],inv[N],g[1<<20][20];
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x<y?x-y+mod:x-y;}
void init(){
fac[0]=1;
for (int i=1;i<N;i++) fac[i]=1ll*i*fac[i-1]%mod;
inv[0]=inv[1]=1;
for (int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for (int i=2;i<N;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;
}
int C(int x,int y){
if (x<0||y<0||x<y) return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++){
scanf("%s",s);
for (int j=0;j<n;j++)if (s[j]=='E') f[j]+=(1<<i);
}
int ans=0;
for (int i=0;i<n;i++) sum[f[i]]++;
init();
for (int i=1;i<=sum[0];i++) ans=add(ans,1ll*C(sum[0],i)*fac[i]%mod);
for (int i=0;i<m;i++) g[0][i]=add(ans,1);
for (int i=1;i<(1<<m);i++){
for (int j=0;j<m;j++){
if (j) g[i][j]=g[i][j-1];
if ((i>>j)&1) g[i][j]=add(g[i][j],g[i^(1<<j)][j]);
}
int s=0;
for (int j=1;j<=sum[i];j++) s=add(s,1ll*C(sum[i],j)*fac[j]%mod);
ans=add(ans,1ll*s*g[i][m-1]%mod);
for (int j=0;j<m;j++) g[i][j]=add(g[i][j],1ll*s*g[i][m-1]%mod);
}
printf("%d\n",ans);
}
/*
11111000
11110000
11000000
10000000
00000000
3!*1!*2!*1!*1!
*/
详细
Test #1:
score: 4.54545
Accepted
time: 0ms
memory: 7660kb
input:
3 1 EHE
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 4.54545
Accepted
time: 2ms
memory: 7636kb
input:
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
output:
33
result:
ok 1 number(s): "33"
Test #3:
score: 4.54545
Accepted
time: 3ms
memory: 6068kb
input:
99930 1 HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...
output:
958738013
result:
ok 1 number(s): "958738013"
Test #4:
score: 4.54545
Accepted
time: 5ms
memory: 7600kb
input:
100000 1 EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...
output:
141886138
result:
ok 1 number(s): "141886138"
Test #5:
score: 4.54545
Accepted
time: 8ms
memory: 11712kb
input:
100000 16 EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...
output:
550365804
result:
ok 1 number(s): "550365804"
Test #6:
score: 4.54545
Accepted
time: 20ms
memory: 13212kb
input:
100000 16 EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...
output:
304783114
result:
ok 1 number(s): "304783114"
Test #7:
score: 4.54545
Accepted
time: 7ms
memory: 11172kb
input:
99913 16 HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...
output:
102498247
result:
ok 1 number(s): "102498247"
Test #8:
score: 4.54545
Accepted
time: 13ms
memory: 12172kb
input:
100000 16 EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...
output:
52676620
result:
ok 1 number(s): "52676620"
Test #9:
score: 4.54545
Accepted
time: 14ms
memory: 15184kb
input:
99989 16 EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...
output:
901615554
result:
ok 1 number(s): "901615554"
Test #10:
score: 4.54545
Accepted
time: 19ms
memory: 13196kb
input:
100000 16 HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...
output:
691375190
result:
ok 1 number(s): "691375190"
Test #11:
score: 4.54545
Accepted
time: 14ms
memory: 11196kb
input:
100000 16 EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...
output:
543699219
result:
ok 1 number(s): "543699219"
Test #12:
score: 4.54545
Accepted
time: 24ms
memory: 15116kb
input:
99990 16 EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...
output:
128876794
result:
ok 1 number(s): "128876794"
Test #13:
score: 4.54545
Accepted
time: 21ms
memory: 13272kb
input:
99912 16 EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...
output:
334603270
result:
ok 1 number(s): "334603270"
Test #14:
score: 4.54545
Accepted
time: 19ms
memory: 11976kb
input:
100000 16 HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...
output:
734499631
result:
ok 1 number(s): "734499631"
Test #15:
score: 4.54545
Accepted
time: 137ms
memory: 90956kb
input:
99985 20 HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...
output:
245101596
result:
ok 1 number(s): "245101596"
Test #16:
score: 4.54545
Accepted
time: 120ms
memory: 90816kb
input:
100000 20 HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...
output:
908982675
result:
ok 1 number(s): "908982675"
Test #17:
score: 4.54545
Accepted
time: 112ms
memory: 91008kb
input:
99974 20 HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...
output:
774998253
result:
ok 1 number(s): "774998253"
Test #18:
score: 4.54545
Accepted
time: 119ms
memory: 90772kb
input:
99916 20 HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...
output:
392464568
result:
ok 1 number(s): "392464568"
Test #19:
score: 4.54545
Accepted
time: 110ms
memory: 90784kb
input:
100000 20 HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...
output:
42780816
result:
ok 1 number(s): "42780816"
Test #20:
score: 4.54545
Accepted
time: 117ms
memory: 91024kb
input:
99908 20 HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...
output:
873687145
result:
ok 1 number(s): "873687145"
Test #21:
score: 4.54545
Accepted
time: 113ms
memory: 90816kb
input:
99923 20 EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...
output:
6819458
result:
ok 1 number(s): "6819458"
Test #22:
score: 4.54545
Accepted
time: 113ms
memory: 91024kb
input:
100000 20 EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...
output:
778489093
result:
ok 1 number(s): "778489093"