#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10, mod = 1e9 + 7;
long long dp[maxn][maxn] , f[maxn] , invf[maxn] , anss;
long long power(int a , int b){
if(b == 0){
return 1;
}
anss = power(a , b/2);
anss *= anss;
anss %= mod;
if(b & 1){
anss *= a;
anss %= mod;
}
return anss;
}
long long c(int n , int k){
return f[n] * invf[k] % mod * invf[n - k] % mod;
}
int main(){
int n , k , cnt = 1 , sizee;
string a[maxn];
bool mark[maxn] , markk[maxn];
vector <int> v;
cin >> n >> k;
for(int i=1 ; i<=n ; i++){
cin >> a[i];
}
for(int i=1 ; i<=n ; i++){
sizee = a[i].size();
for(int j = 0 ; j<sizee ; j++){
mark[a[i][j] - 'a'] = true;
}
for(int j = 1 ; j<=n ; j++){
bool x = true;
if(!markk[j] && j != i){
int sizee = a[j].size();
for(int k = 0 ; k<sizee ; k++){
if(!mark[a[j][k] - 'a']){
x = false;
break;
}
}
if(x){
cnt++;
markk[j] = true;
}
}
}
if(!markk[i]){
v.push_back(cnt);
markk[i] = true;
}
sizee = a[i].size();
for(int j = 0 ; j<sizee ; j++){
mark[a[i][j] - 'a'] = false;
}
cnt = 1;
}
f[0] = invf[0] = 1;
for(int i=1 ; i<maxn ; i++){
f[i] = f[i-1] * i;
f[i] %= mod;
invf[i] = power(f[i] , mod - 2);
}
for(int i=0 ; i<=v[0] ; i++){
int num = (i * (i - 1))/2;
dp[0][num] = c(v[0] , i);
}
sizee = v.size();
for(int i=1 ; i<sizee ; i++){
for(int j=0 ; j<=k ; j++){
int m = 0;
while((m * (m - 1))/2 <= j && m <= v[i]){
dp[i][j] += (dp[i - 1][j - (m * (m - 1))/2] * c(v[i] , m) % mod);
dp[i][j] %= mod;
m++;
}
}
}
sizee = v.size();
cout << (dp[sizee - 1][k] == 0 ? -1 : dp[sizee - 1][k]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
