제출 #142836

#제출 시각아이디문제언어결과실행 시간메모리
142836popovicirobertPIN (CEOI10_pin)C++14
100 / 100
247 ms5860 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...