QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745893 | #5658. Problem Setting | _8_8_# | 13.636364 | 70ms | 18392kb | C++23 | 1.9kb | 2024-11-14 12:16:09 | 2024-11-14 12:16:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e5 + 12, MOD = (int)1e9 + 7;
ll f[N], f1[N], p[N];
int n, m;
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() {
p[0] = f1[0] = f[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;
return ret;
}
void test() {
cin >> n >> m;
prec();
cur.resize(1);
for(int i = 1; i <= n; i++) {
cur[0].push_back(i);
}
for(int i = 0; i < m; i++) {
string s;
cin >> s;
s = "~" + s;
vector<vector<int>> nv;
for(auto v:cur) {
vector<int> e, h;
for(int j:v) {
if(s[j] == 'E') {
e.push_back(j);
} else {
h.push_back(j);
}
}
if(!e.empty()) {
nv.push_back(e);
}
if(!h.empty()) {
nv.push_back(h);
}
}
nv.swap(cur);
}
ll res = 1;
for(auto i:cur) {
int s = (int)i.size();
res *= calc(s);
res %= MOD;
// for(int j:i) {
// cout << j << ' ';
// }
// cout << '\n';
}
res--;
if(res < 0) res += MOD;
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 4.54545
Accepted
time: 0ms
memory: 3824kb
input:
3 1 EHE
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3628kb
input:
10 6 EHEEEHHEEH EHHHEEHHHE EHEHEHEEHH HEHEEEHEEE HHEEHEEEHE EHHEEEEEHE
output:
1279
result:
wrong answer 1st numbers differ - expected: '33', found: '1279'
Test #3:
score: 4.54545
Accepted
time: 13ms
memory: 7432kb
input:
99930 1 HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...
output:
958738013
result:
ok 1 number(s): "958738013"
Test #4:
score: 4.54545
Accepted
time: 13ms
memory: 7444kb
input:
100000 1 EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...
output:
141886138
result:
ok 1 number(s): "141886138"
Test #5:
score: 0
Wrong Answer
time: 39ms
memory: 10388kb
input:
100000 16 EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...
output:
180587689
result:
wrong answer 1st numbers differ - expected: '550365804', found: '180587689'
Test #6:
score: 0
Wrong Answer
time: 39ms
memory: 10376kb
input:
100000 16 EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...
output:
14994791
result:
wrong answer 1st numbers differ - expected: '304783114', found: '14994791'
Test #7:
score: 0
Wrong Answer
time: 39ms
memory: 10336kb
input:
99913 16 HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...
output:
583028851
result:
wrong answer 1st numbers differ - expected: '102498247', found: '583028851'
Test #8:
score: 0
Wrong Answer
time: 39ms
memory: 10428kb
input:
100000 16 EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...
output:
982589643
result:
wrong answer 1st numbers differ - expected: '52676620', found: '982589643'
Test #9:
score: 0
Wrong Answer
time: 35ms
memory: 10408kb
input:
99989 16 EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...
output:
388075409
result:
wrong answer 1st numbers differ - expected: '901615554', found: '388075409'
Test #10:
score: 0
Wrong Answer
time: 40ms
memory: 10624kb
input:
100000 16 HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...
output:
521820679
result:
wrong answer 1st numbers differ - expected: '691375190', found: '521820679'
Test #11:
score: 0
Wrong Answer
time: 35ms
memory: 10488kb
input:
100000 16 EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...
output:
559653051
result:
wrong answer 1st numbers differ - expected: '543699219', found: '559653051'
Test #12:
score: 0
Wrong Answer
time: 34ms
memory: 10564kb
input:
99990 16 EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...
output:
418367029
result:
wrong answer 1st numbers differ - expected: '128876794', found: '418367029'
Test #13:
score: 0
Wrong Answer
time: 34ms
memory: 10384kb
input:
99912 16 EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...
output:
172053229
result:
wrong answer 1st numbers differ - expected: '334603270', found: '172053229'
Test #14:
score: 0
Wrong Answer
time: 31ms
memory: 10448kb
input:
100000 16 HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...
output:
225840002
result:
wrong answer 1st numbers differ - expected: '734499631', found: '225840002'
Test #15:
score: 0
Wrong Answer
time: 57ms
memory: 17328kb
input:
99985 20 HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...
output:
947825737
result:
wrong answer 1st numbers differ - expected: '245101596', found: '947825737'
Test #16:
score: 0
Wrong Answer
time: 69ms
memory: 18196kb
input:
100000 20 HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...
output:
480415481
result:
wrong answer 1st numbers differ - expected: '908982675', found: '480415481'
Test #17:
score: 0
Wrong Answer
time: 62ms
memory: 18140kb
input:
99974 20 HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...
output:
83023032
result:
wrong answer 1st numbers differ - expected: '774998253', found: '83023032'
Test #18:
score: 0
Wrong Answer
time: 62ms
memory: 18392kb
input:
99916 20 HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...
output:
751304225
result:
wrong answer 1st numbers differ - expected: '392464568', found: '751304225'
Test #19:
score: 0
Wrong Answer
time: 70ms
memory: 17916kb
input:
100000 20 HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...
output:
21075122
result:
wrong answer 1st numbers differ - expected: '42780816', found: '21075122'
Test #20:
score: 0
Wrong Answer
time: 62ms
memory: 18128kb
input:
99908 20 HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...
output:
901913861
result:
wrong answer 1st numbers differ - expected: '873687145', found: '901913861'
Test #21:
score: 0
Wrong Answer
time: 65ms
memory: 17848kb
input:
99923 20 EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...
output:
29463921
result:
wrong answer 1st numbers differ - expected: '6819458', found: '29463921'
Test #22:
score: 0
Wrong Answer
time: 68ms
memory: 18128kb
input:
100000 20 EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...
output:
731355968
result:
wrong answer 1st numbers differ - expected: '778489093', found: '731355968'