Submission #2996987


Source Code Expand

Copy
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 998244353

long long int result[1001][1001] = {};
long long int comb[1001][1001] = {};
long long int p[1001] = {};
int cnt[1001] = {};

void getcomb()
{
	for(int i = 0; i < 1001; i++){
		comb[i][0] = 1;
	}
	for(int i = 1; i < 1001; i++){
		for(int j = 1; j <= i; j++){
			comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod;
		}
	}
}

void getp()
{
	for(int i = 1; i < 1001; i++){
		long long int tmpv[31];
		tmpv[0] = i;
		for(int j = 1; j < 31; j++){
			tmpv[j] = (tmpv[j - 1] * tmpv[j - 1]) % mod;
		}
		p[i] = 1;
		int now = mod - 2;
		for(int j = 30; j >= 0; j--){
			if(now >= (1 << j)){
				now -= (1 << j);
				p[i] *= tmpv[j];
				p[i] %= mod;
			}
		}
	}
}

long long int solve(int s, int k)
{
	// s人でグループを作ってもいいよという人がk人いるときの、サイズs以下のグループ分けの方法
	if(result[s][k] >= 0) return result[s][k];
	result[s][k] = 0;
	long long int tmp = 1;
	for(int i = 0; s * i <= k; i++){
		result[s][k] += (tmp * solve(s - 1, k - s * i + cnt[s - 1])) % mod;
		result[s][k] %= mod;
		tmp *= comb[k - s * i][s];
		tmp %= mod;
		tmp *= p[i + 1];
		tmp %= mod;
	}
	// cout << s << " " << k << " " << result[s][k] << endl;
	return result[s][k];
}

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		int a;
		cin >> a;
		cnt[a]++;
	}
	for(int i = 0; i < 1001; i++){
		result[1][i] = 1;
	}
	for(int i = 2; i < 1001; i++){
		for(int j = 0; j < 1001; j++){
			result[i][j] = -1;
		}
	}
	getcomb();
	getp();
	cout << solve(10, cnt[10]) << endl;
}

Submission Info

Submission Time
Task F - チーム分け
User maple
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1978 Byte
Status
Exec Time 7 ms
Memory 15232 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 600 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 7 ms 15232 KB
02.txt 7 ms 15232 KB
03.txt 7 ms 15232 KB
04.txt 7 ms 15232 KB
05.txt 7 ms 15232 KB
06.txt 7 ms 15232 KB
07.txt 7 ms 15232 KB
08.txt 7 ms 15232 KB
09.txt 7 ms 15232 KB
10.txt 7 ms 15232 KB
11.txt 7 ms 15232 KB
12.txt 7 ms 15232 KB
13.txt 7 ms 15232 KB
14.txt 7 ms 15232 KB
15.txt 7 ms 15232 KB
16.txt 7 ms 15232 KB
17.txt 7 ms 15232 KB
18.txt 7 ms 15232 KB
19.txt 7 ms 15232 KB
20.txt 7 ms 15232 KB
21.txt 7 ms 15232 KB
22.txt 7 ms 15232 KB
23.txt 7 ms 15232 KB
24.txt 7 ms 15232 KB
s1.txt 7 ms 15232 KB
s2.txt 7 ms 15232 KB
s3.txt 7 ms 15232 KB