Submission #2996993


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(1000, cnt[1000]) << endl;
}

Submission Info

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

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 600 / 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 33 ms 15232 KB
12.txt 34 ms 15232 KB
13.txt 33 ms 15232 KB
14.txt 32 ms 15232 KB
15.txt 30 ms 15232 KB
16.txt 44 ms 15232 KB
17.txt 44 ms 15232 KB
18.txt 43 ms 15232 KB
19.txt 43 ms 15232 KB
20.txt 42 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