QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119778#5658. Problem Settingpandapythoner#100 ✓1192ms20872kbC++142.2kb2023-07-05 18:13:132024-07-04 00:18:53

Judging History

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

  • [2024-07-04 00:18:53]
  • 评测
  • 测评结果:100
  • 用时:1192ms
  • 内存:20872kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 18:13:13]
  • 提交

answer

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


mt19937 rnd(234);
const ll inf = 1e18;


const ll mod = 1e9+7;


ll bin_pow(ll x, ll n){
    if(n == 0){
        return 1;
    }
    ll a = bin_pow(x, n / 2);
    a = (a * a) % mod;
    if(n & 1){
        a = (a * x) % mod;
    }
    return a;
}



ll rev(ll x){
    return bin_pow(x, mod - 2);
}


vector<ll> f, rvf;

void build_f(int n){
    f.resize(n + 1);
    rvf.resize(n + 1);
    f[0] = rvf[0] = 1;
    for(int i = 1; i <= n; i += 1){
        f[i] = (f[i - 1] * i) % mod;
        rvf[i] = rev(f[i]);
    }
}


ll cnk(ll n, ll k){
    return f[n] * rvf[k] % mod * rvf[n - k] % mod;
}


int n, m;
vector<vector<int>> a;
vector<int> cnt;
vector<int> dp;


int32_t main(){
    if(1){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> m;
    build_f(n);
    a.assign(m, vector<int>(n));
    for(int i = 0; i < m; i += 1){
        for(int j = 0; j < n; j += 1){
            char c;
            cin >> c;
            a[i][j] = (c == 'H');
        }
    }
    cnt.assign(1 << m, 0);
    for(int i = 0; i < n; i += 1){
        ll mask = 0;
        for(int j = 0; j < m; j += 1){
            if(a[j][i]){
                mask += 1 << j;
            }
        }
        cnt[mask] += 1;
    }
    dp.assign(1 << m, 0);
    ll rs = 0;
    for(ll mask = 0; mask < (1 << m); mask += 1){
        if(cnt[mask] >= 1){
            ll t = cnt[mask];
            ll bebra = 0;
            for(int k = 1; k <= t; k += 1){
                bebra = (bebra + cnk(t, k) * f[k] % mod) % mod;
            }
            ll aboba = 0;
            for(int sub_mask = ((mask - 1) & mask); true; sub_mask = ((sub_mask - 1) & mask)){
                aboba = (aboba + dp[sub_mask]) % mod;
                if(sub_mask == 0){
                    break;
                }
            }
            dp[mask] = (aboba + 1) * bebra % mod;
            rs = (rs + dp[mask]) % mod;
        }
    }
    cout << rs << "\n";
    return 0;
}

詳細信息

Test #1:

score: 4.54545
Accepted
time: 0ms
memory: 3808kb

input:

3 1
EHE

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 4.54545
Accepted
time: 0ms
memory: 3580kb

input:

10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

output:

33

result:

ok 1 number(s): "33"

Test #3:

score: 4.54545
Accepted
time: 11ms
memory: 5520kb

input:

99930 1
HHEEHEEHEEEEEHHEEEEHEEHEEEEHEEEEEEEEEEHEEHHHHHEEHEHHHEEHHHEHHHHEEHHEHHHHHHEHEEEHHHHEEHHHEHHEHHEEEEHHHHHEEEHHEHEEEHEEEEHEEHHHEHHHHEHHEEEEHEHEEEEEHEEHHEEHEHEHHEEHEEHHHHEHEEHHHEHEHHHEEEEHEEHEHEHEHHEHHEEHHEEHHEEHEHHEEHHEHEHHEHHHHHEHHHHEEEHHHHEEHEHHHEEEHHEHHEHEHHHEHHEEHEHHEEHEEEHHEHEEEHHHEEEEEHEE...

output:

958738013

result:

ok 1 number(s): "958738013"

Test #4:

score: 4.54545
Accepted
time: 15ms
memory: 5452kb

input:

100000 1
EEEHEHHHEEEEHHEEHHHHEHEEHEEHHEEHEEEEHEEHHEHHHHHHHEEHHHHEEEHEHHEEEEEEEEEHEEEEHEEEEHEHEEHEHHHEEEHHHEEHEEEEEEEEHEEEEHHHHEHHEHHHEEEHHHHHEHEHEHEHEHHHEHHEEEEEHHHHEHHEEHHEHHEHHEEHEEEHHEEHEEHEHHHEHHEHHHEHEHHEEHEHHHEEHHEHEEHHEEHHHHEEHHHHHEHEEHHEHHEHHEEEHEHEEEHHEHEHHEHEHEEEHHHEEHHEHEEHHEHHHHEEEHHHEHE...

output:

141886138

result:

ok 1 number(s): "141886138"

Test #5:

score: 4.54545
Accepted
time: 157ms
memory: 11436kb

input:

100000 16
EHEEEHEHHEEEEEHHHEHHHEEHHHHEHEHEEEHHEEHHEHEEHHEEEEEEHHEEHHEHHHHEHHEEEEHEEEEHHEHHEEEEEHHHEHEEHEHEEEHEHHHHEEHHEHHEHEHEEEEEHHEHHEEEHEEEHHHEHEEEHHEEHEHHEHHHEEHHHEHHEHEEHHEEEHHEHEHHHEHEEHHHHHEHHHEHHEEEEEHEEHEHHEHHHEHHHEHHHEHHHEEEEHHEHHEEHHHEEHHEEHHEHHEEEEEEHHHEHHEEEEHEHEHEEEHEHHEEHHEHHEHHEEHEHE...

output:

550365804

result:

ok 1 number(s): "550365804"

Test #6:

score: 4.54545
Accepted
time: 161ms
memory: 11372kb

input:

100000 16
EHEHEHHEHEEEEEHEHHEHEEEHEEHHEEEEHHEEEHEEEHEEEEEEEHHHHEHEEHEEEHEEEEHHEEHHEEHHHEHEEHEEEEHEEEEEEEHEHHEEEHHHEHHHHHEEEEEHHEHEHHHHHHHHEEHEHHHHEHEHHEEEEHHHEHEEHEEEHEEEEHHHHHHEHEEHHEHHHEEEEHEEEHEHEEEHHEHHEHHHEHEEHHHEEEEHHHEEEEEEHEHEHEHEHHHEHHHHHHEHHEEEEEHHEHHHHHEEHEEHHHHHEHHHEEEHHEHEEHHHHHEEEEHEHH...

output:

304783114

result:

ok 1 number(s): "304783114"

Test #7:

score: 4.54545
Accepted
time: 160ms
memory: 11520kb

input:

99913 16
HEHHHEEEHEEEEEEHHEEEHHEHEEEEEEHHHHEHEEHEEHHHHEEEHHEEHEHEHHHEHEHHEEHEEEEHEEHEHEHHEEHEHHHEHEHEHEEHEEHEEHHHEHHEEHEHHEHEEEEEEEEEEHHHHHHEEHHHHEEHEHEHHHHEEHEEHHHHEEEHEEHHHEEHHEHEHEEHHHHHEEEHHEEEEEEEEHEHHHEHHHHEHHHEHEEEEEEEEEEHEEEEEEHEEHEHEHHHEEEHHHEHEEHEEHHHEHEEEHHHEEEEHEHHEEHEEEHEHEHEHHHEEHHEEEH...

output:

102498247

result:

ok 1 number(s): "102498247"

Test #8:

score: 4.54545
Accepted
time: 153ms
memory: 11520kb

input:

100000 16
EHEHEHEHHHHEHEHEHEEEHEEEEHEHEEHHEHHEEHHEHEHEHEEHEHEHHEEEHHEHHEHHEHEEHEHEHHEEEEEHHEEHEHHHEHHEHHEHHEHHEEHEHHHHHEHHHHEHEEEEHHHEHEHEEHHHHEEHHEHHHEHHEEHHEEHHEEEEEHEEHHEHEEHHEEHEEEEEHEHEEHEHHHHEHEEHEEEHHEEEEEHEHEEHEEEEEEHEEHEHEEEHEEEHEEHHHHEEHEHHEHEHEEHHHEHEHEHHHEEEHEEHEEEHEEEHHHEEEEEEEEEHEHEEEE...

output:

52676620

result:

ok 1 number(s): "52676620"

Test #9:

score: 4.54545
Accepted
time: 162ms
memory: 11352kb

input:

99989 16
EEEHEHEEEHHEHHEHHEHEEHEHEHHEEHEEEEEHEHHEEEHEHEHEHEHHHEHEEEEHHHEHHHHEHHEEHEHHHEHHHHHHHEHEHHHEHEHEEHHEHEHHEEEHEHHEEEEEEEHEHHEEEEEHHHHHHEHHHEHEHHEHHHHHEHEHHHEEEEEEEHEHEEEEHEHEEHHHHEHEEHHHEEEEHEHEHHEHEHHEHEEHHHHEHHEHHEHHEEEEEHHHEEHHEHEEHEHEEHHHHEHHHHEEHEHEEEHEEEHHHHEHEEHHEHEHHHHEEHHHEHEHHEHEEHH...

output:

901615554

result:

ok 1 number(s): "901615554"

Test #10:

score: 4.54545
Accepted
time: 159ms
memory: 11332kb

input:

100000 16
HHEHHEHEEHEHEEHEEEEHHHEEHHHHEEHEEHHHEHHHHEEHEEHEHHHHHHHHHHEHEHEEEEHEEEEEHHHEEHEHEEHEEEEEEHHHHEHEHEEHHHHHEEHEEHHHEEHEEHEEEEHEEEEHHHHHEEHHHHEEHHEEHHHEHEHHHHHHHEEEEEHHHEEHHHEEHEHHHEEHHEEEHHHHEHHEHEHEHEHEEHEEEHHHHHEHHEEEEHEEEHHHHEHEHEHHEEEEEHHEEHHHHEEEHEEHHHEEHHEEEEEEEHHHHHHEHHHHHEHEEHHHHHHHHH...

output:

691375190

result:

ok 1 number(s): "691375190"

Test #11:

score: 4.54545
Accepted
time: 160ms
memory: 11348kb

input:

100000 16
EEHEHHEEHHEHEHHHEEHEHEHEEEEHHEEEHHEEHHHEEEEHEEHHHEEHHEEHEHEHHEEHEHHEEEHEEHHHEHEEHHEHEEHHHEHEEEEEHEEHHHHEEEEEEHHHEEHHEHHHEEHHEHHHEEEEEHHHHEHHHEHEEHEEHHEEHEHHHEHEHHHHHEHHEEEHEEHHEEHHEHEEEEHEEHHHEHEHHHEEEEHHHHEHEHEEEHEHHEHEHHHHEEEEHHHEEEHEHHEHHEHHEHEEEEHEHEHHEHHHHEEHHEHEHEHHEHEEEHHHHEEHHHHEHH...

output:

543699219

result:

ok 1 number(s): "543699219"

Test #12:

score: 4.54545
Accepted
time: 153ms
memory: 11516kb

input:

99990 16
EEEEEHHHEEHHEEEHHEHEEHHHHHHHEHHEHEEEHEHEHEEHEHHEEHHEHHEEHEEEHHHHEHHHHEEHEHHHEEEEEEHEHEEEEEEHHHHHEEHEHEHHEHEHEEEHHHHHHEHHEEEEEEHEEHEHHHHHHEHEHHEHHHEEEEHEHEEHHEHEEHHHHHHEHEEHEEHHHEHHEHHEEHEHEHHEEHHHEHHHEHEHEHEEEEHHHHHEEHHEHHHHHHHEHEEHHEHEHEEEHEEHEHHHEEEHEEHHHEEHEEEHEEHEEHHHHEHHHHHEHEEHEHHEHHH...

output:

128876794

result:

ok 1 number(s): "128876794"

Test #13:

score: 4.54545
Accepted
time: 156ms
memory: 11296kb

input:

99912 16
EHEEEEHHEEEHEHHEEHHEHEEEHHEHHEEEHEHEHHEHEEHEHHHEEEEHHHHEHHEEHEEHEHHHEEEHHEHHEHEEHEEEHHHEEEEEHHEEHEHHEEEHHHHEHHEEEHHHEHEHEEEEEHHHEEEHHEHEHHHHHEHHEEEHHHEEEHHEEEEHHEHEHHHHHHHEHEEEEHHEHEEEHEHEEEEHHHHEHEHEEEEHEHEEEEHHEHEEHEHHHHEHHHHEHHHEEHEEEHHEHHHHHHEHEEEEEHHHHEHEHHHEHHHHEEHEHHHEEEHEEEEHHEEEEEH...

output:

334603270

result:

ok 1 number(s): "334603270"

Test #14:

score: 4.54545
Accepted
time: 157ms
memory: 11360kb

input:

100000 16
HHEEHHEEHHEHHEEEEHEHEHHEEHEEHHEHHHHEHHEEEEEHHEEHHEHEEHHEHHEEEHHEEHEEEHHEEEHHEHHHHHHHHEEEHHEHHEHHEEEHEEEEEEEEEHHEEHEHHEHHEEEHHEHEEHHHHHHEEEHHEEEEHHEEEEHHEEHHHEHHEEEHEEEEHEEEHHEHEHEHEEEHHHEEHEEHHHEEHHEEHEHEEEHEHEHHHEHHHEEHEEHEHHEEEHHHEEEHEHEHEEEHEHHEEEEEEHHHEHHEHHEEEHHHEEEHHEHEHEHEHHHHEEEHHH...

output:

734499631

result:

ok 1 number(s): "734499631"

Test #15:

score: 4.54545
Accepted
time: 1192ms
memory: 20732kb

input:

99985 20
HHEEHEHHEEHHEHEEHEEEHEEHHHEHEHHEHEHEHEHEHEEEHEEHHHEEEEHHEEHHHHEEEEEHHHEEEHHEHHEHEEHHEEHEEHEEHHHEHEHEHHHHEEHEEHEHHEEHEHHEHHEEHEEEHHEEHHEEEEEEEHEHEEHEEEEEHHEHEEHEHEHEEHHEEHEHHEEHEEEHHHEHEEHHEEHEHEHEHHEEEHHEEEEEEEEHEHHHHHHEEHEHHHHEEEEEEEEHHEHEHHHHHEEHEEHEEHHHEHEEEHHHHEHEHEHHEEHEHEEEEHHHHHHEEEH...

output:

245101596

result:

ok 1 number(s): "245101596"

Test #16:

score: 4.54545
Accepted
time: 1170ms
memory: 20868kb

input:

100000 20
HHEHHEEEHEEEEEEHHEEHEHHEHHHHEEEHHHEHHEHEEEEHHHHHHEHHHHHEHEHEHEEEHHEEEHEEHHEHEHHHEHEHEEEHHEEEHHEEHEHHEEHEEEHEHEEHHEEEEEHEEEEHHHHHHHHHHHEHHHHHHEEEHEHEHHEEEEHHHHEEHHEEHEHEHHHEHEEHHEEHEHHEHEEHHHHEEHHHEHHHHEEHHHHHEEEEEEEEEEHEEHEHHHHEEHEHEHHEEEEHHHHHEEEHHHHHHHHHHEEHEHEHEEHEEEHHHEEEEEHHEEEEHEEHHE...

output:

908982675

result:

ok 1 number(s): "908982675"

Test #17:

score: 4.54545
Accepted
time: 1178ms
memory: 20712kb

input:

99974 20
HHEEHEEEHEHEHEHEHHHEEHEEEHHHHEHHHHHHEHEHHHEEEHEEEHHHEHHEEEHEHEHEEHEHHEHHEEEEHEEHHHHEHEEHHEHHEEEHEEHEHEEEEHHEEEEHHHEHEEHEEHEEHEEHHHHHEHEEHEHEEHHEHHEEHEEHEEEHEHHHHHEEEEHEEHHHHEHHHHEHHEEEHEEHHHEHHEEEHHEHHEHHEEEEHHEHHEHEHHEHEEHHEEHEHEHEEEEEHEEEHEEEEHEHHHHHHHHHEHHHHEHHHEEHEHEHEEEHEHHHEHEHHHHHHHH...

output:

774998253

result:

ok 1 number(s): "774998253"

Test #18:

score: 4.54545
Accepted
time: 1175ms
memory: 20872kb

input:

99916 20
HEHHHHEHEHEHEHHHEHEEEHHEEEHEHHEEEHEEHEEHEEHEHHHHHHEHHEEEEEEEHHEEHEHHHEEEEEEHEHEHEEEHHHEHHHEHHEHHEEHHHEEHHHHHHEHEHHEHHEHHHHEHEEEHHHHEHEEEEEEEHEHHEHEEHEEEEHEHHHEEHEEEHEHEEEHHHEEEEEEHHHHHHHHHHHHEEEHHEHHEHHEEEHEEEEHHHEEEEHHHEEEEHEHEEHHEEEEHEEEHHEHEEHHEEEHEHEEEHEEHEEEHHHEHEHHEHEEEHHHEEEEEHHEHHEH...

output:

392464568

result:

ok 1 number(s): "392464568"

Test #19:

score: 4.54545
Accepted
time: 1175ms
memory: 20712kb

input:

100000 20
HEHEHEHEHEEEHHEHEHHHEHHEEEEEEHEEHHEEEHEHHHHEHHEHHHEHEHEHEEEEEHEEHHEHEEHHHHHEHEHEHEHHHHHHHHHEHEHEHHHHEEEHEEEHHEHEEHEHHHEHHHEHEEHHHEEEEHEHEHHEHEHEEHHEEHHHEEHEHHEHEHHEEHEHHHHEEEEHHEEHEEEEHHEEHHEHHEHEEHEEEEEHEHEHHHHEHHHHEHEHEHEEEHEEHEHHHHHHHEHHHHEEEEHHHEEEEHEHEHHEEEHHEEEHEHEHEEEEHEEHEEHHEEEEEE...

output:

42780816

result:

ok 1 number(s): "42780816"

Test #20:

score: 4.54545
Accepted
time: 1185ms
memory: 20700kb

input:

99908 20
HHEHHEEEHHHHHEHHHEEHHEHEHEHHHHEEEEEEHEEHHHHHEEEEEEEHEHEEHHEHEHEEEEHEEHEHEEEEHEHHHEHHEHHHEEHHHHEHEHHHEHHHEHHHEEHHHEEEEHEHEEEHHEEEEEHHEEHEHEEEHEEHEHHHEEHHHEHHHEEEEHEEEEHHEHEHEHHHHEHEEHEEHEHHHEEHHHHEHEHHHHHHHHEEEHHEHEHHHHEEHEHEHEHHHEEHEHEHEEHEEEHEHHEEHEEEEEHHHHEHEHHEHHHHHEHHHHEHEHEHEEHEEEEHHEE...

output:

873687145

result:

ok 1 number(s): "873687145"

Test #21:

score: 4.54545
Accepted
time: 1176ms
memory: 20704kb

input:

99923 20
EHEHEHHEHHEHEEEHEEHHHEHHHHHHHEEEEHEEHEHEEHEEEHEHEHHHEEHEEHHHHHEEHHHHEHEEEEHEEEHEEHEHHEHHEHEEHHEEEHHHHHEEEEHEEEHHHHHHHEEEEHHHEEEHHHEEHHHEEHHHHHHEHEHHEHEEEHHEHHHEEHHHHEHEEHHEEEHHEHEHHEHHEHEHHEEHHEHEHHEEEEHHEHHEHHEHHEHEEEEHEHEEHEHHHHEHHHEHEEEEHHHEHEEHEHEEEHHEEHEHHHHHEEHEHEEHHHHHEHHEHHHHEHHHHEE...

output:

6819458

result:

ok 1 number(s): "6819458"

Test #22:

score: 4.54545
Accepted
time: 1184ms
memory: 20788kb

input:

100000 20
EHEEHEHEHHEEEHHHEEEHEHHEHEHEHEHEEEHHEHEHEHEHEHEEHEEEHEEEHEEEEEEEHHEEHHHEEEHEEHHHEEHEHEEEEHHHEEEHEHHHEHHEEEEEEHHEEEEEEEEHHEEHHEHEEHHHEEHEEEEEHEHHHHHEEHHEEHEEHHEEHEHHHEEHEHEHEEEEEHHEEEHHHHEEHHEEHEEEEEEEEHHEHEEHEHHEEHHEHHHHHEEEHHEEEEEHHHHEHHHHEHHHHEEHEEHEHEEHHHHEEEEHHEEEHEHEHEEHHHHEEEHHHHEHEE...

output:

778489093

result:

ok 1 number(s): "778489093"