/*
<< in the name of Allah >>
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
#define ps push_back
#define pb pop_back
#define mp make_pair
#define all(x) x.begin() , x.end()
#define sz(x) (int)x.size()
#define debug(a) cout<<"debug: "<<(#a)<<" = "<<a<<'\n'
#define debugAr(a) cout << "Array " << (#a) << " :\n" ;for (int TMP : a) cout << TMP << " " ; cout << '\n' ;
const ll maxn = 2e3 + 10 , mod = 1e9 + 7 ;
ll dp[maxn][maxn] ;
ll n , k ;
ll C[maxn][maxn] ;
map<string , ll> cnt ;
int main()
{
ios::sync_with_stdio(false) ;
cin.tie(NULL) ;
cout.tie(NULL) ;
/*for (int r = 0 ; r < maxn ; r++)
C[0][r] = 0 ;*/
for (ll i = 0 ; i < maxn ; i++)
C[i][0] = 1ll ;
for (ll N = 1 ; N < maxn ;N++){
for (ll r = 1 ; r < maxn ; r++){
C[N][r] = C[N-1][r] + C[N-1][r-1] ;
C[N][r] %= mod ;
}
}
cin >> n >> k ;
for (ll i = 0 ; i < n ; i++){
string t ;
cin >> t ;
sort(all(t)) ;
cnt[t] ++ ;
}
ll ind = 1 ;
dp[0][0] = 1 ;
for (pair<string , ll> x : cnt){
ll Cnt = x.second ;
debug(Cnt) ;
/*if (ind == 1){
for (ll j = 0 ;j <= Cnt ; j++){
dp[1][C[j][2]] += C[Cnt][j] ;
dp[1][C[j][2]] %= mod ;
}
ind ++ ;
continue ;
}*/
for (ll i = 0 ; i <= k ; i++){
for (ll j = 0 ; j <= Cnt ; j++){
ll idx = i-C[j][2] ;
if (idx < 0)continue ;
ll temp = dp[ind-1][idx]*C[Cnt][j] ; temp %= mod ;
dp[ind][i] += temp ;
dp[ind][i] %= mod ;
}
}
ind ++ ;
}
cout << (dp[ind-1][k]%mod) << '\n' ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
31852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
32044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
31852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
