Submission #1192120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192120		SmuggingSpun	Anagramistica (COCI21_anagramistica)	C++20	110 / 110	12 ms	16204 KiB

anagramistica

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int lim = 2e3 + 5;
const int mod = 1e9 + 7;
void add(int& a, int b){
	if((a += b) >= mod){
		a -= mod;
	}
}
int Ckn[lim][lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	memset(Ckn, 0, sizeof(Ckn));
	for(int n = Ckn[0][0] = 1; n < lim; n++){
		Ckn[0][n] = 1;
		for(int k = 1; k <= n; k++){
			Ckn[k][n] = (Ckn[k][n - 1] + Ckn[k - 1][n - 1]) % mod;
		}
	}
	int n, k;
	cin >> n >> k;
	map<vector<int>, int>cnt;
	for(int _ = 0; _ < n; _++){
		vector<int>a(26, 0);
		string s;
		cin >> s;
		for(char& c : s){
			a[c - 97]++;
		}
		cnt[a]++;
	}
	vector<int>dp(k + 1, 0);
	dp[0] = 1;
	for(auto& [u, v] : cnt){
		vector<int>ndp = dp;
		for(int i = 1; i <= v; i++){
			for(int j = k, bound_j = (i * (i - 1)) >> 1; j >= bound_j; j--){
				add(ndp[j], 1LL * dp[j - bound_j] * Ckn[i][v] % mod);
			}
		}
		swap(dp, ndp);
	}
	cout << dp[k];
}

Compilation message (stderr)

anagramistica.cpp: In function 'int main()':
anagramistica.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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