답안 #142836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
142836 2019-08-11T12:01:28 Z popovicirobert PIN (CEOI10_pin) C++14
100 / 100
247 ms 5860 KB
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long


/*const int MOD = 998244353;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

vector <string> str;
int n;
bool mark[5];

ll solve(int step, int last) {
    if(step == 0) {
        vector <string> all;
        for(int i = 0; i < n; i++) {
            string cur;
            for(int j = 0; j < 4; j++) {
                if(mark[j] == 0)
                    cur.push_back(str[i][j]);
            }
            all.push_back(cur);
        }
        sort(all.begin(), all.end());
        ll ans = 0;
        int i = 0;
        while(i < n) {
            int j = i;
            while(j < n && all[i] == all[j]) {
                j++;
            }
            ans += 1LL * (j - i - 1) * (j - i) / 2;
            i = j;
        }
        return ans;
    }
    else {
        if(last == 3) return 0;
        ll ans = 0;
        for(int i = last + 1; i < 4; i++) {
            mark[i] = 1;
            ans += solve(step - 1, i);
            mark[i] = 0;
        }
        return ans;
    }
}

int comb[10][10];

inline void prec() {
    int i, j;
    for(i = 0; i < 10; i++) {
        comb[i][0] = 1;
        for(j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, d;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> d;
    str.resize(n);
    for(auto &it : str) {
        cin >> it;
    }

    prec();

    vector <ll> ways(5);
    for(i = 0; i <= 4; i++) {
        ways[i] = solve(i, -1);
        for(j = i - 1; j >= 0; j--) {
            ways[i] -= ways[j] * comb[4 - j][4 - i];
        }
    }
    cout << ways[d];

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 92 ms 2796 KB Output is correct
5 Correct 113 ms 3184 KB Output is correct
6 Correct 112 ms 3124 KB Output is correct
7 Correct 93 ms 2760 KB Output is correct
8 Correct 124 ms 3252 KB Output is correct
9 Correct 211 ms 5464 KB Output is correct
10 Correct 235 ms 5836 KB Output is correct
11 Correct 119 ms 3216 KB Output is correct
12 Correct 219 ms 5616 KB Output is correct
13 Correct 136 ms 3424 KB Output is correct
14 Correct 124 ms 3356 KB Output is correct
15 Correct 223 ms 5676 KB Output is correct
16 Correct 174 ms 4752 KB Output is correct
17 Correct 247 ms 5828 KB Output is correct
18 Correct 192 ms 5012 KB Output is correct
19 Correct 223 ms 5480 KB Output is correct
20 Correct 247 ms 5860 KB Output is correct