Submission #19562

#	Time	Username	Problem	Language	Result	Execution time	Memory
19562		tncks0121	목공 (kriii4_A)	C++14	4 / 100	55 ms	1396 KiB

A

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

#define debug(format, ...) printf(format, __VA_ARGS__);

const ll MOD = (521ll << 21) + 1;

ll modpow (ll a, ll b) {
    a %= MOD;
    ll ret = 1;
    while(b > 0) {
        if(b & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return ret;
}

struct mint {
    ll val;
    mint(ll val = 0): val((val % MOD + MOD) % MOD) { }
    mint operator+(mint p) { return val + p.val; }
    mint operator-(mint p) { return val - p.val; }
    mint operator*(mint p) { return val * p.val; }
    mint operator/(mint p) { return val * modpow(p.val, MOD-2); }
};

const int N_ = 16050;
int N, M;

int Q[N_], sumQ;
mint invsumQ;

mint P[N_];

mint tb[N_];

int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++) scanf("%d", Q+i);

	sumQ = accumulate(Q, Q+N, 0);
	invsumQ = mint(1) / sumQ;
	for(int i = 0; i < N; i++) P[i] = mint(Q[i]) * invsumQ;

	for(int x = N; x <= M; x++) {
		tb[x] = 1;
		for(int i = 0; i < N; i++) 
			tb[x] = tb[x] + tb[x - N + i] * P[i];
	}

	printf("%lld\n", tb[M].val);
    return 0;
}

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