oj.uz

답안 #679735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679735 2023-01-09T05:34:24 Z amir Anagramistica (COCI21_anagramistica) C++14
10 / 110
 16 ms 32980 KB 
/*
<< 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 + 3 , 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 (int i = 0 ; i < maxn ; i++) 
		C[i][0] = 1 ;
	for (int N = 1 ; N < maxn ;N++){
		for (int r = 1 ; r < maxn ; r++)
			C[N][r] = C[N-1][r] + C[N-1][r-1] ;
	}
	
	cin >> n >> k ;
	for (int i = 0 ; i < n ; i++){
		string t ;
		cin >> t ;
		sort(all(t)) ;
		cnt[t] ++ ;
	}
	int ind = 1 ;
	for (pair<string , int> x : cnt){
		ll Cnt = x.second ;
		if (ind == 1){
			for (int j = 0 ;j <= Cnt ; j++){
				dp[1][C[j][2]] += C[Cnt][j] ;
			}
			ind ++ ;
			continue ;
		}
		//debug(Cnt) ;
		for (int i = 0 ; i <= k ; i++){
			for (int j = 0 ; j <= Cnt ; j++){
				int idx = i-C[j][2] ;
				if (idx < 0)continue ;
				ll temp = dp[ind-1][idx]*C[Cnt][j] ; temp %= mod ;
				dp[ind][i] += temp ;
			}
		}
		ind ++ ;
	}
	cout << dp[ind-1][k] << '\n' ;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31700 KB Output is correct
2 Correct 15 ms 31720 KB Output is correct
3 Correct 16 ms 31768 KB Output is correct
4 Correct 15 ms 31636 KB Output is correct
5 Correct 15 ms 31644 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31932 KB Output is correct
2 Correct 16 ms 32980 KB Output is correct
3 Incorrect 16 ms 31860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 31700 KB Output is correct
2 Correct 15 ms 31720 KB Output is correct
3 Correct 16 ms 31768 KB Output is correct
4 Correct 15 ms 31636 KB Output is correct
5 Correct 15 ms 31644 KB Output is correct
6 Correct 15 ms 31932 KB Output is correct
7 Correct 16 ms 32980 KB Output is correct
8 Incorrect 16 ms 31860 KB Output isn't correct
9 Halted 0 ms 0 KB -