Submission #20076

#	Time	Username	Problem	Language	Result	Execution time	Memory
20076		gs13068	목공 (kriii4_A)	C++98	4 / 100	24 ms	1104 KiB

A

#include <cstdio>
#include <map>

const int p = 1092616193;

using namespace std;

int f(int x, int y)
{
	return y & 1 ? (long long)f(x, y ^ 1)*x%p : y ? f((long long)x*x%p, y >> 1) : 1;
}

int a[1001];
int d[5005];

int main()
{
	int i, j, n, m, t, s = 0;
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
	{
		scanf("%d", a + i);
		s += a[i];
	}
	s = f(s, p - 2);
	for (i = n; i <= m; i++)
	{
		t = 0;
		for (j = 0; j < n; j++) t = (t + (long long)a[j] * d[i + j - n]) % p;
		d[i] = ((long long)t * s + 1) % p;
	}
	printf("%d", d[m]);
}

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