QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94844 | #5658. Problem Setting | Purslane | 4.545455 | 1023ms | 48900kb | C++14 | 1.5kb | 2023-04-07 23:23:18 | 2023-04-07 23:23:22 |
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+dp[i][0])%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: 0
Wrong Answer
time: 985ms
memory: 33736kb
input:
3 1 EHE
output:
61
result:
wrong answer 1st numbers differ - expected: '9', found: '61'
Test #2:
score: 4.54545
Accepted
time: 1007ms
memory: 33532kb
input:
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
output:
33
result:
ok 1 number(s): "33"
Test #3:
score: 0
Wrong Answer
time: 1000ms
memory: 33060kb
input:
99930 1 HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...
output:
785626270
result:
wrong answer 1st numbers differ - expected: '958738013', found: '785626270'
Test #4:
score: 0
Wrong Answer
time: 988ms
memory: 32624kb
input:
100000 1 EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...
output:
674958411
result:
wrong answer 1st numbers differ - expected: '141886138', found: '674958411'
Test #5:
score: 0
Wrong Answer
time: 1009ms
memory: 39060kb
input:
100000 16 EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...
output:
536536416
result:
wrong answer 1st numbers differ - expected: '550365804', found: '536536416'
Test #6:
score: 0
Wrong Answer
time: 983ms
memory: 34312kb
input:
100000 16 EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...
output:
915259141
result:
wrong answer 1st numbers differ - expected: '304783114', found: '915259141'
Test #7:
score: 0
Wrong Answer
time: 1015ms
memory: 33460kb
input:
99913 16 HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...
output:
239201606
result:
wrong answer 1st numbers differ - expected: '102498247', found: '239201606'
Test #8:
score: 0
Wrong Answer
time: 1023ms
memory: 38728kb
input:
100000 16 EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...
output:
17090107
result:
wrong answer 1st numbers differ - expected: '52676620', found: '17090107'
Test #9:
score: 0
Wrong Answer
time: 1000ms
memory: 33596kb
input:
99989 16 EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...
output:
542956347
result:
wrong answer 1st numbers differ - expected: '901615554', found: '542956347'
Test #10:
score: 0
Wrong Answer
time: 997ms
memory: 34060kb
input:
100000 16 HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...
output:
69967610
result:
wrong answer 1st numbers differ - expected: '691375190', found: '69967610'
Test #11:
score: 0
Wrong Answer
time: 994ms
memory: 33636kb
input:
100000 16 EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...
output:
947629677
result:
wrong answer 1st numbers differ - expected: '543699219', found: '947629677'
Test #12:
score: 0
Wrong Answer
time: 998ms
memory: 39136kb
input:
99990 16 EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...
output:
246635340
result:
wrong answer 1st numbers differ - expected: '128876794', found: '246635340'
Test #13:
score: 0
Wrong Answer
time: 996ms
memory: 33568kb
input:
99912 16 EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...
output:
769295082
result:
wrong answer 1st numbers differ - expected: '334603270', found: '769295082'
Test #14:
score: 0
Wrong Answer
time: 992ms
memory: 39072kb
input:
100000 16 HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...
output:
584685340
result:
wrong answer 1st numbers differ - expected: '734499631', found: '584685340'
Test #15:
score: 0
Wrong Answer
time: 1007ms
memory: 48760kb
input:
99985 20 HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...
output:
204197341
result:
wrong answer 1st numbers differ - expected: '245101596', found: '204197341'
Test #16:
score: 0
Wrong Answer
time: 999ms
memory: 46716kb
input:
100000 20 HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...
output:
516543716
result:
wrong answer 1st numbers differ - expected: '908982675', found: '516543716'
Test #17:
score: 0
Wrong Answer
time: 1022ms
memory: 48900kb
input:
99974 20 HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...
output:
37398989
result:
wrong answer 1st numbers differ - expected: '774998253', found: '37398989'
Test #18:
score: 0
Wrong Answer
time: 1011ms
memory: 46752kb
input:
99916 20 HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...
output:
805196414
result:
wrong answer 1st numbers differ - expected: '392464568', found: '805196414'
Test #19:
score: 0
Wrong Answer
time: 1019ms
memory: 48748kb
input:
100000 20 HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...
output:
307887853
result:
wrong answer 1st numbers differ - expected: '42780816', found: '307887853'
Test #20:
score: 0
Wrong Answer
time: 1001ms
memory: 46852kb
input:
99908 20 HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...
output:
805006532
result:
wrong answer 1st numbers differ - expected: '873687145', found: '805006532'
Test #21:
score: 0
Wrong Answer
time: 1000ms
memory: 46804kb
input:
99923 20 EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...
output:
429882111
result:
wrong answer 1st numbers differ - expected: '6819458', found: '429882111'
Test #22:
score: 0
Wrong Answer
time: 1022ms
memory: 46760kb
input:
100000 20 EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...
output:
669040528
result:
wrong answer 1st numbers differ - expected: '778489093', found: '669040528'