제출 #443700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443700		Wasif_Jamil	Zapina (COCI20_zapina)	C++14	110 / 110	330 ms	3268 KiB

zapina

// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int ncr[351][351];
int dp[351][351][2];
int n;

void fillncr(int n){
	ncr[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			if(j > i)ncr[i][j] = 0;
			else if(j == i || j == 0)ncr[i][j] = 1;
			else ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%mod;
		}
	}
}

int f(int persons, int tasks, int is_valid){
	if(persons == n){
		return (is_valid | (tasks == persons));
	}
	if(tasks == 0){
		return is_valid;
	}
	if(dp[persons][tasks][is_valid] != -1)return dp[persons][tasks][is_valid];
	int ways = 0;
	for(int i=0; i<=tasks; i++){
		ways += f(persons+1, tasks-i, is_valid|(persons == i)) * ncr[tasks][i];
		ways %= mod;
	}
	return dp[persons][tasks][is_valid] = ways % mod;
}

signed main(){
	memset(dp, -1, sizeof dp);
	fillncr(350);
	cin >> n;
	int val = f(1, n, 0);
	cout << val << '\n';
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55