제출 #386874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
386874		phathnv	Anagramistica (COCI21_anagramistica)	C++11	110 / 110	19 ms	19436 KiB

anagramistica

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2007;
const int MOD = 1e9 + 7;

int n, k, numWord, c[N];
int nCk[N][N], dp[N][N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    map<string, int> cnt;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        cnt[s]++;
    }
    for(auto p : cnt)
        c[++numWord] = p.second;

    for(int i = 0; i <= n; i++){
        nCk[i][0] = 1;
        for(int j = 1; j <= i; j++)
            nCk[i][j] = (nCk[i - 1][j] + nCk[i - 1][j - 1]) % MOD;
    }
    dp[0][0] = 1;
    for(int i = 0; i < numWord; i++)
        for(int j = 0; j <= k; j++)
            for(int x = 0; x <= c[i + 1]; x++){
                int nxtJ = j + x * (x - 1) / 2;
                if (nxtJ <= k)
                    dp[i + 1][nxtJ] = (dp[i + 1][nxtJ] + (ll) dp[i][j] * nCk[c[i + 1]][x] % MOD) % MOD;
            }
    cout << dp[numWord][k];
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70