QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94843#5658. Problem SettingPurslane18.181818 264ms48856kbC++141.4kb2023-04-07 23:14:472023-04-07 23:14:48

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:14:48]
  • 评测
  • 测评结果:18.181818
  • 用时:264ms
  • 内存:48856kb
  • [2023-04-07 23:14:47]
  • 提交

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,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]=wys[i*U+j]*tmp[j]%MOD;
		ffor(j,0,U) {
			int tot=0;
			for(int k=j;k;k=(k-1)&j) 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;
		ffor(j,0,U) tmp[j]=(tmp[j]+dp[i][j])%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: 239ms
memory: 34312kb

input:

3 1
EHE

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 4.54545
Accepted
time: 244ms
memory: 32584kb

input:

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

output:

33

result:

ok 1 number(s): "33"

Test #3:

score: 4.54545
Accepted
time: 236ms
memory: 35960kb

input:

99930 1
HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...

output:

958738013

result:

ok 1 number(s): "958738013"

Test #4:

score: 4.54545
Accepted
time: 235ms
memory: 33216kb

input:

100000 1
EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...

output:

141886138

result:

ok 1 number(s): "141886138"

Test #5:

score: 0
Wrong Answer
time: 254ms
memory: 36616kb

input:

100000 16
EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...

output:

582224683

result:

wrong answer 1st numbers differ - expected: '550365804', found: '582224683'

Test #6:

score: 0
Wrong Answer
time: 240ms
memory: 33688kb

input:

100000 16
EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...

output:

774614272

result:

wrong answer 1st numbers differ - expected: '304783114', found: '774614272'

Test #7:

score: 0
Wrong Answer
time: 251ms
memory: 33200kb

input:

99913 16
HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...

output:

957173428

result:

wrong answer 1st numbers differ - expected: '102498247', found: '957173428'

Test #8:

score: 0
Wrong Answer
time: 255ms
memory: 33236kb

input:

100000 16
EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...

output:

350933453

result:

wrong answer 1st numbers differ - expected: '52676620', found: '350933453'

Test #9:

score: 0
Wrong Answer
time: 231ms
memory: 38920kb

input:

99989 16
EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...

output:

76653756

result:

wrong answer 1st numbers differ - expected: '901615554', found: '76653756'

Test #10:

score: 0
Wrong Answer
time: 256ms
memory: 34232kb

input:

100000 16
HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...

output:

410943047

result:

wrong answer 1st numbers differ - expected: '691375190', found: '410943047'

Test #11:

score: 0
Wrong Answer
time: 251ms
memory: 33396kb

input:

100000 16
EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...

output:

649060490

result:

wrong answer 1st numbers differ - expected: '543699219', found: '649060490'

Test #12:

score: 0
Wrong Answer
time: 259ms
memory: 38792kb

input:

99990 16
EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...

output:

137126647

result:

wrong answer 1st numbers differ - expected: '128876794', found: '137126647'

Test #13:

score: 0
Wrong Answer
time: 255ms
memory: 33440kb

input:

99912 16
EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...

output:

424402759

result:

wrong answer 1st numbers differ - expected: '334603270', found: '424402759'

Test #14:

score: 0
Wrong Answer
time: 239ms
memory: 33256kb

input:

100000 16
HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...

output:

381981170

result:

wrong answer 1st numbers differ - expected: '734499631', found: '381981170'

Test #15:

score: 0
Wrong Answer
time: 260ms
memory: 46816kb

input:

99985 20
HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...

output:

872174985

result:

wrong answer 1st numbers differ - expected: '245101596', found: '872174985'

Test #16:

score: 0
Wrong Answer
time: 263ms
memory: 46840kb

input:

100000 20
HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...

output:

59754174

result:

wrong answer 1st numbers differ - expected: '908982675', found: '59754174'

Test #17:

score: 0
Wrong Answer
time: 236ms
memory: 47040kb

input:

99974 20
HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...

output:

182565208

result:

wrong answer 1st numbers differ - expected: '774998253', found: '182565208'

Test #18:

score: 0
Wrong Answer
time: 257ms
memory: 46712kb

input:

99916 20
HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...

output:

900567270

result:

wrong answer 1st numbers differ - expected: '392464568', found: '900567270'

Test #19:

score: 0
Wrong Answer
time: 264ms
memory: 46676kb

input:

100000 20
HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...

output:

91776533

result:

wrong answer 1st numbers differ - expected: '42780816', found: '91776533'

Test #20:

score: 0
Wrong Answer
time: 261ms
memory: 46884kb

input:

99908 20
HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...

output:

989222884

result:

wrong answer 1st numbers differ - expected: '873687145', found: '989222884'

Test #21:

score: 0
Wrong Answer
time: 249ms
memory: 48856kb

input:

99923 20
EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...

output:

607148709

result:

wrong answer 1st numbers differ - expected: '6819458', found: '607148709'

Test #22:

score: 0
Wrong Answer
time: 256ms
memory: 46768kb

input:

100000 20
EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...

output:

468252768

result:

wrong answer 1st numbers differ - expected: '778489093', found: '468252768'