#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10, mod = 1e9 + 7;
long long dp[maxn][maxn] , c[maxn][maxn];
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;
}
for(int i = 0 ; i<maxn ; i++){
c[0][i] = 1;
}
for(int i=1 ; i<maxn ; i++){
for(int j=1 ; j<maxn ; j++){
c[i][j] = c[i - 1][j - 1] + c[i][j - 1];
c[i][j] %= mod;
}
}
for(int i=0 ; i<=v[0] ; i++){
int num = (i * (i - 1))/2;
dp[0][num] = c[i][v[0]];
}
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[m][v[i]] % 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 |
36 ms |
31916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
32076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
31916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
