CP Lang
16 lines0.3 spec// coci20c6p3 Anagramistica: choose a subset of words with exactly k similar (anagram) pairs. Only
// the sizes of anagram classes matter: taking c words from a class of s gives choose(s, c) ways
// and c(c - 1) / 2 pairs, a knapsack over the classes.
type Z = Mod<1_000_000_007>
let (n, k) = read<(1..=2_000, 0..=2_000)>()
let sizes = read<[n]Str>().tally(by: s => s.sorted()).values.collect()
domain G = sizes.keys
let comb = Comb<Z>(n)
@memo(array)
fn ways(g: G.cuts, left: 0..=k) -> Z:
if g == G.cuts.last!:
return if left == 0: 1 else: 0
let s = sizes[g.r!]
(0..=s).take_while(c => c * (c - 1) / 2 <= left)
.map(c => comb.choose(s, c) * ways(g.next!, left - c * (c - 1) / 2)).sum()
print(ways(G.cuts.first!, k))
Accepted C++
102 lines · 0.27 s on the judge#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...) 1412
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
using Key = array<int, 26>;
const long mod = 1e9 + 7;
const int maxn = 2e3 + 5;
long choose[maxn + 1][maxn + 1];
void pcomp() {
for (int i = 0; i <= maxn; i++) {
choose[i][0] = choose[i][i] = 1;
for (int j = 1; j < i; j++) {
choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
if (choose[i][j] >= mod) {
choose[i][j] -= mod;
}
}
}
}
void solve() {
int n, k;
cin >> n >> k;
map<Key, int> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
Key key {};
for (auto& a : s) {
key[a - 'a']++;
}
m[key]++;
}
vector<int> arr;
for (auto& [_, v] : m) {
dbg(v);
arr.push_back(v);
}
auto c2 = [&](int x) -> int {
return x * (x - 1) / 2;
};
n = sz(arr);
long dp[n + 1][k + 1] {};
dp[n][k] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= k; j++) {
for (int cnt = 0; cnt <= arr[i]; cnt++) {
int cj = j + c2(cnt);
if (cj > k) {
break;
}
dp[i][j] = (dp[i][j] + choose[arr[i]][cnt] * dp[i + 1][cj]) % mod;
}
dbg(i, j, dp[i][j]);
}
}
cout << dp[0][0] << endl;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
pcomp();
int t = 1;
// cin >> t;
for (int _ = 1; _ <= t; _++) {
dbg(_);
// cout << "Case #" << _ << ": ";
solve();
}
}