#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll md = 1e9 + 7;
const int lim = 20001;
struct combination{
vector<vector<ll>> ncr;
combination(int k){
ncr = vector<vector<ll>>(k, vector<ll>(k, 0));
for(int i = 0; i < k; i++) ncr[i][0] = 1;
for(int i = 1; i < k; i++) for(int j = 1; j <= i; j++) ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%md;
}
};
inline ll pw(ll x, ll p){
if(p == 0) return 1;
if(p%2 == 0) return((x*x)%md, p/2);
return (pw(x, p-1)*x)%md;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<ll> nn(lim);
vector<vector<pair<ll, ll>>> s(lim);
for(int i = 0; i < lim; i++) nn[i] = (ll)i*(i-1)/2;
for(int i = 0; i < lim; i++) for(int j = 0; j < lim; j++) if(nn[i]+nn[j] < lim) s[nn[i]+nn[j]].pb({i, j});
int n, k; cin >> n >> k;
vector<str> v(n);
for(str &s: v){
cin >> s;
sort(s.begin(), s.end());
}
sort(v.begin(), v.end());
vector<int> sth;
ll ans = 0, p = 0;
for(int i = 0; i < n; i++){
if(i != 0 && v[i] == v[i-1]){
sth.back()++;
}
else{
sth.pb(1);
}
}
n = sth.size();
combination cmb(2500);
vector<vector<ll>> dp(n, vector<ll>(k+2, 0));
for(int i = n-1; i >= 0; i--){
ll c = sth[i];
for(int ki = 0; ki <= k; ki++){
for(auto [a, b]: s[ki]){
if(a > c) continue;
if(a != 0) a++;
if(b != 0) b++;
ll x = a*(a-1)/2, y = b*(b-1)/2;
if(x == ki && i == n-1 && b == 0){
dp[i][ki]+=cmb.ncr[c][a];
dp[i][ki]%=md;
continue;
}
//if(ki == 0 && i == 1) cout << a << " " << b << " " << cmb.ncr[c][a]*dp[2][y] << "d\n";
if(i == n-1) continue;
dp[i][ki]+=(cmb.ncr[c][a]*dp[i+1][y])%md;
dp[i][ki]%=md;
}
}
}
ans = dp[0][k+1];
ans%=md;
cout << ans << "\n";
}
Compilation message
anagramistica.cpp: In function 'll pw(ll, ll)':
anagramistica.cpp:20:30: warning: left operand of comma operator has no effect [-Wunused-value]
20 | if(p%2 == 0) return((x*x)%md, p/2);
| ~~~~~^~~
anagramistica.cpp: In function 'int main()':
anagramistica.cpp:38:17: warning: unused variable 'p' [-Wunused-variable]
38 | ll ans = 0, p = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
272 ms |
50724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
282 ms |
50728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
272 ms |
50724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
