Submission #475225

#	Time	Username	Problem	Language	Result	Execution time	Memory
475225		keta_tsimakuridze	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	124 ms	6612 KiB

anagramistica

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t,n,k,dp[N],fact[N],invfact[N];
map<string,int> cnt;
string s[N];
int C(int a,int b) {
	if(a < b) return 0;
	return fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}
int pwr(int u,int v) {
	int ans = 1;
	while(v) {
		if(v%2) ans = ans * u % mod;
		v /= 2;
		u = u * u % mod;
	}
	return ans;
}
main(){
	cin >> n >> k;
	fact[0] = invfact[0] = 1;
	for(int i = 1; i <= n; i++) {
		cin >> s[i];
		sort(s[i].begin(),s[i].end());
		cnt[s[i]]++;
		fact[i] = fact[i - 1] * i % mod;
		invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
	}
	dp[0] = 1;
	for(int i = 1; i <= n; i++) {
	
		for(int j = k; j >= 0; j--) {
			for(int p = 1; p <= cnt[s[i]]; p++) {
				if(p * (p - 1) / 2 <= j)dp[j] = (dp[j] + dp[j - p * (p - 1)/2] * C(cnt[s[i]],p)) % mod;
		}}

		cnt[s[i]] = 0;
	}
	cout << dp[k];
 }

Compilation message (stderr)

anagramistica.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~

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