Submission #9742

#	Time	Username	Problem	Language	Result	Execution time	Memory
9742		myungwoo	The last wizard (kriii2_T)	C++14	1 / 4	144 ms	262144 KiB

T

#include <stdio.h>
#include <vector>
using namespace std;

#define MAXN 10004
typedef long long lld;

const int MOD = 1e9 + 7;
int T, N, A, none, ans;
int P[MAXN][10], Q[MAXN];

void dfs(int t, vector <int> &v, int p)
{
	int i, j;
	if (t == T){
		int x = 1;
		for (i=0;i<10;i++) x = (lld)x*v[i]%MOD;
		ans = (ans+(lld)x*p%MOD)%MOD;
		return;
	}
	for (i=1;i<=N;i++){
		for (j=0;j<10;j++) v[j] = (v[j]+P[i][j])%MOD;
		dfs(t+1, v, (lld)p*Q[i]%MOD);
		for (j=0;j<10;j++) v[j] = (v[j]-P[i][j]+MOD)%MOD;
	}
	dfs(t+1, v, (lld)p*none%MOD);
}

int main()
{
	int i, j, k;
	scanf("%d%d%d", &T, &N, &A);
	none = A;
	for (i=1;i<=N;i++){
		scanf("%d", Q+i);
		for (j=0;j<10;j++){
			scanf("%d", P[i]+j);
		}
		none -= Q[i];
	}
	vector <int> arr(10,1);
	dfs(0, arr, 1);
	printf("%d\n", ans);
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3