QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94846 | #5658. Problem Setting | Purslane | 18.181818 | 1089ms | 49032kb | C++14 | 1.5kb | 2023-04-07 23:26:58 | 2023-04-07 23:27:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXM=1050,MAXK=(1<<20)+10,MOD=1e9+7;
int Mx=(1<<20)+4,n,m,fuc[MAXK],inv[MAXK],val[MAXK],cnt[MAXK],wys[MAXK],dp[MAXM][MAXM],tmp[MAXM];
int qpow(int base,int p) {
int ans=1;
while(p) {
if(p&1) ans*=base,ans%=MOD;
base*=base,base%=MOD,p>>=1;
}
return ans;
}
int C(int u,int d) {
return fuc[d]*inv[u]%MOD*inv[d-u]%MOD;
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
fuc[0]=1; ffor(i,1,Mx) fuc[i]=fuc[i-1]*i%MOD;
inv[Mx]=qpow(fuc[Mx],MOD-2);
roff(i,Mx-1,0) inv[i]=inv[i+1]*(i+1)%MOD;
cin>>n>>m;
ffor(i,1,m) {
string S; cin>>S; S="&"+S;
ffor(j,1,n) if(S[j]=='H') val[j]+=(1<<i-1);
}
ffor(i,1,n) cnt[val[i]]++;
ffor(i,0,Mx) ffor(j,1,cnt[i]) wys[i]=(wys[i]+C(j,cnt[i])*fuc[j]%MOD)%MOD;
int U=(1<<10)-1,ans=0;
ffor(i,0,U) tmp[i]=1;
ffor(i,0,U) {
ffor(j,0,U) {
dp[i][j]=1;
ffor(k,0,i-1) if((k&i)==k) dp[i][j]=(dp[i][j]+dp[k][j])%MOD;
dp[i][j]=dp[i][j]*wys[i*U+j]%MOD;
}
ffor(j,0,U) {
int tot=0;
ffor(k,0,j) if((k&j)==k) tot=(tot+dp[i][k])%MOD;
tot=(tot-dp[i][j])%MOD;
tot=tot*wys[i*U+j]%MOD;
dp[i][j]=(dp[i][j]+tot)%MOD;
}
ffor(j,0,9) ffor(k,0,U-(1<<j)) if(!(k&(1<<j))) dp[i][k+(1<<j)]=(dp[i][k+(1<<j)]+dp[i][k])%MOD;
ans=(ans+dp[i][U])%MOD;
}
cout<<(ans%MOD+MOD)%MOD<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.54545
Accepted
time: 1051ms
memory: 33152kb
input:
3 1 EHE
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 4.54545
Accepted
time: 1064ms
memory: 32552kb
input:
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
output:
33
result:
ok 1 number(s): "33"
Test #3:
score: 4.54545
Accepted
time: 1069ms
memory: 32580kb
input:
99930 1 HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...
output:
958738013
result:
ok 1 number(s): "958738013"
Test #4:
score: 4.54545
Accepted
time: 1076ms
memory: 32696kb
input:
100000 1 EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...
output:
141886138
result:
ok 1 number(s): "141886138"
Test #5:
score: 0
Wrong Answer
time: 1075ms
memory: 38824kb
input:
100000 16 EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...
output:
277319069
result:
wrong answer 1st numbers differ - expected: '550365804', found: '277319069'
Test #6:
score: 0
Wrong Answer
time: 1062ms
memory: 38932kb
input:
100000 16 EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...
output:
583066730
result:
wrong answer 1st numbers differ - expected: '304783114', found: '583066730'
Test #7:
score: 0
Wrong Answer
time: 1059ms
memory: 33516kb
input:
99913 16 HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...
output:
164965859
result:
wrong answer 1st numbers differ - expected: '102498247', found: '164965859'
Test #8:
score: 0
Wrong Answer
time: 1070ms
memory: 33268kb
input:
100000 16 EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...
output:
665659108
result:
wrong answer 1st numbers differ - expected: '52676620', found: '665659108'
Test #9:
score: 0
Wrong Answer
time: 1071ms
memory: 36460kb
input:
99989 16 EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...
output:
26930891
result:
wrong answer 1st numbers differ - expected: '901615554', found: '26930891'
Test #10:
score: 0
Wrong Answer
time: 1074ms
memory: 39076kb
input:
100000 16 HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...
output:
960761657
result:
wrong answer 1st numbers differ - expected: '691375190', found: '960761657'
Test #11:
score: 0
Wrong Answer
time: 1053ms
memory: 34352kb
input:
100000 16 EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...
output:
696811375
result:
wrong answer 1st numbers differ - expected: '543699219', found: '696811375'
Test #12:
score: 0
Wrong Answer
time: 1074ms
memory: 38788kb
input:
99990 16 EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...
output:
55620366
result:
wrong answer 1st numbers differ - expected: '128876794', found: '55620366'
Test #13:
score: 0
Wrong Answer
time: 1083ms
memory: 33448kb
input:
99912 16 EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...
output:
372720470
result:
wrong answer 1st numbers differ - expected: '334603270', found: '372720470'
Test #14:
score: 0
Wrong Answer
time: 1059ms
memory: 33472kb
input:
100000 16 HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...
output:
768651169
result:
wrong answer 1st numbers differ - expected: '734499631', found: '768651169'
Test #15:
score: 0
Wrong Answer
time: 1065ms
memory: 46688kb
input:
99985 20 HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...
output:
957258016
result:
wrong answer 1st numbers differ - expected: '245101596', found: '957258016'
Test #16:
score: 0
Wrong Answer
time: 1086ms
memory: 46896kb
input:
100000 20 HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...
output:
463737453
result:
wrong answer 1st numbers differ - expected: '908982675', found: '463737453'
Test #17:
score: 0
Wrong Answer
time: 1077ms
memory: 49032kb
input:
99974 20 HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...
output:
438296895
result:
wrong answer 1st numbers differ - expected: '774998253', found: '438296895'
Test #18:
score: 0
Wrong Answer
time: 1065ms
memory: 46776kb
input:
99916 20 HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...
output:
441690568
result:
wrong answer 1st numbers differ - expected: '392464568', found: '441690568'
Test #19:
score: 0
Wrong Answer
time: 1064ms
memory: 46812kb
input:
100000 20 HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...
output:
950494807
result:
wrong answer 1st numbers differ - expected: '42780816', found: '950494807'
Test #20:
score: 0
Wrong Answer
time: 1089ms
memory: 46800kb
input:
99908 20 HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...
output:
427824379
result:
wrong answer 1st numbers differ - expected: '873687145', found: '427824379'
Test #21:
score: 0
Wrong Answer
time: 1059ms
memory: 46768kb
input:
99923 20 EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...
output:
889796486
result:
wrong answer 1st numbers differ - expected: '6819458', found: '889796486'
Test #22:
score: 0
Wrong Answer
time: 1067ms
memory: 46772kb
input:
100000 20 EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...
output:
553766785
result:
wrong answer 1st numbers differ - expected: '778489093', found: '553766785'