QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#747718 | #5658. Problem Setting | _8_8_ | 13.636364 | 81ms | 65416kb | C++23 | 1.7kb | 2024-11-14 17:59:57 | 2024-11-14 17:59:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)(1 << 20) + 12, MOD = (int)1e9 + 7;
ll f[N], f1[N], p[N];
int n, m;
ll dp[N], c[N];
string s[N];
vector<vector<int>> cur;
ll binpow(ll a, ll b) {
ll ret = 1, k = a;
while(b) {
if(b & 1) {
ret *= k;
ret %= MOD;
}
k *= k;
k %= MOD;
b /= 2;
}
return ret;
}
void prec() {
f1[0] = f[0] = 1;
p[0] = 1;
for(int i = 1; i <= n; i++) {
f[i] = f[i - 1] * 1ll * i % MOD;
f1[i] = binpow(f[i], MOD - 2);
p[i] = p[i - 1] + f1[i];
if(p[i] >= MOD) p[i] -= MOD;
}
}
ll calc(ll s) {
ll ret = f[s] * p[s] % MOD;
ret--;
if(ret < 0) ret += MOD;
return ret;
}
void test() {
cin >> n >> m;
prec();
for(int i = 0; i < m; i++) {
cin >> s[i];
}
for(int i = 0; i < n; i++) {
int f = 0;
for(int j = 0; j < m; j++) {
if(s[j][i] == 'H') {
f += (1 << j);
}
}
c[f]++;
}
for(int i = 0; i < (1 << m); i++) {
dp[i] = calc(c[i]);
}
for(int i = 0; i < m; i++) {
for(int j = (1 << m) - 1; j >= 0; j--) {
if(!((j >> i) & 1)) {
dp[j] += (dp[j + (1 << i)] * calc(c[j])) % MOD;
if(dp[j] >= MOD) dp[j] -= MOD;
}
}
}
ll res = 0;
for(int i = 0; i < (1 << m); i++) {
res += dp[i];
if(res >= MOD) res -= MOD;
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4.54545
Accepted
time: 0ms
memory: 45376kb
input:
3 1 EHE
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Wrong Answer
time: 3ms
memory: 46060kb
input:
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
output:
15
result:
wrong answer 1st numbers differ - expected: '33', found: '15'
Test #3:
score: 4.54545
Accepted
time: 12ms
memory: 45752kb
input:
99930 1 HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...
output:
958738013
result:
ok 1 number(s): "958738013"
Test #4:
score: 4.54545
Accepted
time: 18ms
memory: 45640kb
input:
100000 1 EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...
output:
141886138
result:
ok 1 number(s): "141886138"
Test #5:
score: 0
Wrong Answer
time: 25ms
memory: 47416kb
input:
100000 16 EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...
output:
616587170
result:
wrong answer 1st numbers differ - expected: '550365804', found: '616587170'
Test #6:
score: 0
Wrong Answer
time: 27ms
memory: 47384kb
input:
100000 16 EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...
output:
712605723
result:
wrong answer 1st numbers differ - expected: '304783114', found: '712605723'
Test #7:
score: 0
Wrong Answer
time: 27ms
memory: 47752kb
input:
99913 16 HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...
output:
337946627
result:
wrong answer 1st numbers differ - expected: '102498247', found: '337946627'
Test #8:
score: 0
Wrong Answer
time: 23ms
memory: 47324kb
input:
100000 16 EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...
output:
110029223
result:
wrong answer 1st numbers differ - expected: '52676620', found: '110029223'
Test #9:
score: 0
Wrong Answer
time: 27ms
memory: 47068kb
input:
99989 16 EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...
output:
454990081
result:
wrong answer 1st numbers differ - expected: '901615554', found: '454990081'
Test #10:
score: 0
Wrong Answer
time: 25ms
memory: 46852kb
input:
100000 16 HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...
output:
414093735
result:
wrong answer 1st numbers differ - expected: '691375190', found: '414093735'
Test #11:
score: 0
Wrong Answer
time: 24ms
memory: 56268kb
input:
100000 16 EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...
output:
301330765
result:
wrong answer 1st numbers differ - expected: '543699219', found: '301330765'
Test #12:
score: 0
Wrong Answer
time: 26ms
memory: 47456kb
input:
99990 16 EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...
output:
679856567
result:
wrong answer 1st numbers differ - expected: '128876794', found: '679856567'
Test #13:
score: 0
Wrong Answer
time: 23ms
memory: 56352kb
input:
99912 16 EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...
output:
248452596
result:
wrong answer 1st numbers differ - expected: '334603270', found: '248452596'
Test #14:
score: 0
Wrong Answer
time: 31ms
memory: 47772kb
input:
100000 16 HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...
output:
836672091
result:
wrong answer 1st numbers differ - expected: '734499631', found: '836672091'
Test #15:
score: 0
Wrong Answer
time: 75ms
memory: 60060kb
input:
99985 20 HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...
output:
307629
result:
wrong answer 1st numbers differ - expected: '245101596', found: '307629'
Test #16:
score: 0
Wrong Answer
time: 67ms
memory: 59704kb
input:
100000 20 HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...
output:
312849
result:
wrong answer 1st numbers differ - expected: '908982675', found: '312849'
Test #17:
score: 0
Wrong Answer
time: 76ms
memory: 60788kb
input:
99974 20 HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...
output:
311203
result:
wrong answer 1st numbers differ - expected: '774998253', found: '311203'
Test #18:
score: 0
Wrong Answer
time: 72ms
memory: 59508kb
input:
99916 20 HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...
output:
308604
result:
wrong answer 1st numbers differ - expected: '392464568', found: '308604'
Test #19:
score: 0
Wrong Answer
time: 77ms
memory: 65416kb
input:
100000 20 HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...
output:
310049
result:
wrong answer 1st numbers differ - expected: '42780816', found: '310049'
Test #20:
score: 0
Wrong Answer
time: 64ms
memory: 59536kb
input:
99908 20 HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...
output:
306418
result:
wrong answer 1st numbers differ - expected: '873687145', found: '306418'
Test #21:
score: 0
Wrong Answer
time: 81ms
memory: 65140kb
input:
99923 20 EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...
output:
307377
result:
wrong answer 1st numbers differ - expected: '6819458', found: '307377'
Test #22:
score: 0
Wrong Answer
time: 72ms
memory: 60440kb
input:
100000 20 EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...
output:
311715
result:
wrong answer 1st numbers differ - expected: '778489093', found: '311715'