Submission #20015

#	Time	Username	Problem	Language	Result	Execution time	Memory
20015		tonyjjw	목공 (kriii4_A)	C++14	4 / 100	13 ms	1784 KiB

A

//*
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <functional>
#define MOD 1092616193
#define MAX 0x3f3f3f3f
#define MAX2 0x3f3f3f3f3f3f3f3fll
#define ERR 1e-10
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)
using namespace std;

typedef long long ll;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

ll mul_inv(ll a, ll b=MOD)
{
	ll b0=b, t, q;
	ll x0=0, x1=1;
	if(b == 1) return 1;
	while(a > 1)
	{
		q=a/b;
		t=b, b=a%b, a=t;
		t=x0, x0=x1-q*x0, x1=t;
	}
	if(x1 < 0) x1+=b0;
	return x1;
}


int n, m;
ll p[2000];
ll d[6000];

int main()
{
	int i, j, k;
	cin>>n>>m;
	ll sum=0;
	for(i=0;i<n;i++)
	{
		scanf("%lld", &p[i]);
		sum+=p[i];
	}
	for(i=0;i<n;i++) p[i]*=mul_inv(sum), p[i]%=MOD;
	for(i=n;i<=m;i++)
	{
		ll sum=0;
		for(j=0;j<=n-1;j++)
		{
			sum+=d[i-(n-j)]*p[j]%MOD;
		}
		sum++;
		sum%=MOD;
		d[i]=sum;
	}
	cout<<d[m];
	return 0;
}
//*/

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