제출 #142836

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142836		popovicirobert	PIN (CEOI10_pin)	C++14	100 / 100	247 ms	5860 KiB

pin

#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;
}

• Subtask 1: 100 / 100