oj.uz

Submission #679732

# Submission time Handle Problem Language Result Execution time Memory
679732 2023-01-09T04:58:31 Z parsadox2 Anagramistica (COCI21_anagramistica) C++14
110 / 110
 12 ms 14316 KB 
#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e3 + 10 , mod = 1e9 + 7;

int n , k , dp[maxn] , cnt[maxn] , val[maxn] , C[maxn][maxn];
string ar[maxn];

int32_t main()
{
	fast;
	
	C[0][0] = 1;
	for(int i = 1 ; i < maxn ; i++)
	{
		C[i][0] = 1;
		for(int j = 1 ; j <= i ; j++)
		{
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
	}
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++)
	{
		cin >> ar[i];
		sort(ar[i].begin() , ar[i].end());
	}
	sort(ar , ar + n);
	int ps = 1;
	cnt[ps] = 1;
	for(int i = 1 ; i < n ; i++)
	{
		if(ar[i] != ar[i - 1])
			ps++;
		cnt[ps]++;
	}
	dp[0] = 1;
	for(int i = 1 ; i <= ps ; i++)
	{
		for(int j = k ; j > -1 ; j--)
		{
			for(int num = 1 ; num <= cnt[i] ; num++)
			{
				if(j < C[num][2])
					break;
				dp[j] = (dp[j] + 1LL * C[cnt[i]][num] * dp[j - C[num][2]] % mod) % mod;
			}
		}
	}
	cout << dp[k] << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 9 ms 14236 KB Output is correct
4 Correct 9 ms 14304 KB Output is correct
5 Correct 9 ms 14300 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14292 KB Output is correct
2 Correct 9 ms 14296 KB Output is correct
3 Correct 9 ms 14308 KB Output is correct
4 Correct 10 ms 14316 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14288 KB Output is correct
3 Correct 9 ms 14236 KB Output is correct
4 Correct 9 ms 14304 KB Output is correct
5 Correct 9 ms 14300 KB Output is correct
6 Correct 9 ms 14292 KB Output is correct
7 Correct 9 ms 14296 KB Output is correct
8 Correct 9 ms 14308 KB Output is correct
9 Correct 10 ms 14316 KB Output is correct
10 Correct 9 ms 14224 KB Output is correct
11 Correct 9 ms 14292 KB Output is correct
12 Correct 9 ms 14292 KB Output is correct
13 Correct 10 ms 14292 KB Output is correct
14 Correct 10 ms 14312 KB Output is correct
15 Correct 9 ms 14316 KB Output is correct
16 Correct 10 ms 14208 KB Output is correct
17 Correct 12 ms 14288 KB Output is correct
18 Correct 9 ms 14292 KB Output is correct