QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#747718#5658. Problem Setting_8_8_13.636364 81ms65416kbC++231.7kb2024-11-14 17:59:572024-11-14 17:59:57

Judging History

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

  • [2024-11-14 17:59:57]
  • 评测
  • 测评结果:13.636364
  • 用时:81ms
  • 内存:65416kb
  • [2024-11-14 17:59:57]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'