Submission #494605

#	Time	Username	Problem	Language	Result	Execution time	Memory
494605		Nimbostratus	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	11 ms	14240 KiB

anagramistica

#include "bits/stdc++.h"
#define fi first
#define se second
constexpr int maxn = 2e3 + 5;
constexpr int inf = 2e9;
constexpr int mod = 1e9 + 7;
using namespace std;
using lint = long long;
using pii = pair<int, int>;

int n, k;
int knap[2][maxn];
int c[maxn][maxn];
map<string, int> mp;
int m;
int sz[maxn];
vector<pii> p[maxn];

void precalc() {
	for(int i = 0; i <= n; i++)
		c[i][0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	m = mp.size();
	for(int i = 1; i <= m; i++) {
		sz[i] = mp.begin()->se;
		mp.erase(mp.begin());
		for(int j = 1; j <= sz[i]; j++)
			p[i].push_back({c[sz[i]][j], c[j][2]});
	}
}

void solve() {
	knap[1][0] = 1;
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j <= k; j++)
			knap[0][j] = knap[1][j];
		for(auto [num, cnt] : p[i])
			for(int j = k - cnt; j >= 0; j--) {
				knap[1][j + cnt] += 1ll * num * knap[0][j] % mod;
				knap[1][j + cnt] %= mod;
			}
	}
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		string str;
		cin >> str;
		sort(str.begin(), str.end());
		mp[str]++;
	}
	precalc();
	solve();
	cout << knap[1][k] << endl;

}

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