QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94846#5658. Problem SettingPurslane18.181818 1089ms49032kbC++141.5kb2023-04-07 23:26:582023-04-07 23:27:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 23:27:01]
  • 评测
  • 测评结果:18.181818
  • 用时:1089ms
  • 内存:49032kb
  • [2023-04-07 23:26:58]
  • 提交

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'