Submission #19047

#	Time	Username	Problem	Language	Result	Execution time	Memory
19047		kriii	목공 (kriii4_A)	C++14	4 / 100	475 ms	1184 KiB

A

#include <stdio.h>

const long long mod = 1092616193;

long long fpow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p >>= 1;
	}
	return r;
}

int main()
{
	int N,Q[16006];
	long long M,S=0; scanf ("%d %lld",&N,&M);
	for (int i=0;i<N;i++){
		scanf ("%d",&Q[i]);
		S += Q[i];
	}
	long long v = fpow(S,-1);
	
	const int sz = 20000;
	long long A[sz] = {0,};
	for (int i=N;i<=M;i++){
		long long &a = A[i%sz];
		a = 0;
		for (int j=0;j<N;j++) a = (a + A[i-N+j] * Q[j]) % mod;
		a = a * v % mod;
		a++;
		if (a >= mod) a = 0;
	}
	printf ("%lld\n",A[M%sz]);

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 96