Submission #19046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19046	2016-02-17T09:42:23 Z	kriii	목공 (kriii4_A)	C++14	100 / 100	3195 ms	49320 KB

A

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

const int maxL = 18;
const int maxN = 1 << maxL;
long long mod = 1092616193;
long long generator = 3;
long long root[maxN], invroot[maxN];
int rev[maxL+1][maxN];

inline long long add(long long a, long long b)
{
	a += b;
	if (a >= mod)
		a -= mod;
	return a;
}

inline long long mul(long long a, long long b)
{
	return a * b % mod;
}

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 get_rev(int a, int u)
{
	int r = 0;
	u--;
	while (u){
		r <<= 1;
		r += a & 1;
		a >>= 1;
		u >>= 1;
	}
	return r;
}

void init()
{
	root[0] = invroot[0] = 1;
	root[1] = fpow(generator, (mod - 1) / maxN);
	invroot[1] = fpow(root[1], -1);
	for (int j = 2; j<maxN; j++){
		root[j] = mul(root[j - 1], root[1]);
		invroot[j] = mul(invroot[j - 1], invroot[1]);
	}
	for (int l=0;l<=maxL;l++){
		for (int i=0;i<(1<<l);i++) rev[l][i] = get_rev(i,(1<<l));
	}
}

vector<long long> fft(long long *root, int *rev, vector<long long> input)
{
	int n = input.size();
	vector<long long> res(n);
	for (int i = 0; i < n; i++) res[rev[i]] = input[i];
	for (int i = 2, h = 1, u = maxN >> 1; i <= n; i <<= 1, h <<= 1, u >>= 1){
		for (int k = 0; k < n; k += i){
			for (int j = 0; j < h; j++){
				long long w = root[u*j];
				long long t = mul(w, res[k + j + h]);
				long long u = res[k + j];
				res[k + j] = add(u, t);
				res[k + j + h] = add(u, mod - t);
			}
		}
	}
	return res;
}

void poly_norm(vector<long long> &a)
{
	while (!a.empty() && a.back() == 0) a.pop_back();
}

vector<long long> poly_mul(vector<long long> a, vector<long long> b)
{
	vector<long long> c;
	int al = a.size(), bl = b.size(), n = 1, l = 0;
	while (n < al + bl - 1) n *= 2, l++;
	if (n <= 32){
		c = vector<long long>(n,0);
		for (int i=0;i<al;i++) for (int j=0;j<bl;j++) c[i+j] = (c[i+j] + a[i] * b[j]) % mod;
	}
	else{
		a.resize(n); b.resize(n);
		vector<long long> A = fft(root,rev[l],a);
		vector<long long> B = fft(root,rev[l],b);
		for (int i=0;i<n;i++) A[i] = mul(A[i],B[i]);
		c = fft(invroot,rev[l],A);
		long long invn = fpow(n,-1);
		for (int i=0;i<n;i++) c[i] = mul(c[i],invn);
	}
	c.resize(al+bl-1);
	return c;
}

vector<long long> poly_sqr(vector<long long> a)
{
	vector<long long> c;
	int al = a.size(), n = 1, l = 0;
	while (n < al * 2 - 1) n *= 2, l++;
	if (n <= 32){
		c = vector<long long>(n,0);
		for (int i=0;i<al;i++) for (int j=0;j<al;j++) c[i+j] = (c[i+j] + a[i] * a[j]) % mod;
	}
	else{
		a.resize(n);
		vector<long long> A = fft(root,rev[l],a);
		for (int i=0;i<n;i++) A[i] = mul(A[i], A[i]);
		c = fft(invroot,rev[l],A);
		long long invn = fpow(n,-1);
		for (int i=0;i<n;i++) c[i] = mul(c[i],invn);
	}
	c.resize(al*2-1);
	return c;
}

vector<long long> poly_div(vector<long long> a, vector<long long> b)
{
	poly_norm(a);
	poly_norm(b);
	if (a.size() < b.size() || b.empty()) return a;
	int l = a.size() - b.size() + 1, s = b.size() - 1;
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	if (b[0] != 1){
		long long u = fpow(b[0],-1);
		for (auto &x : b) x = mul(x,u);
	}

	vector<long long> h(1,1);
	int lev = 1;
	while (lev < l){
		lev *= 2;
		vector<long long> p = b; p.resize(lev);
		vector<long long> q = poly_sqr(h);
		vector<long long> g = poly_mul(p,q);
		h.resize(lev);
		for (int i=0;i<lev;i++){
			h[i] = add(h[i],h[i]);
			h[i] = add(h[i],mod-g[i]);
		}
	}

	vector<long long> c = poly_mul(a,h);
	c.resize(l);
	
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	reverse(c.begin(),c.end());
	b = poly_mul(b,c);
	for (int i=0;i<s;i++) a[i] = add(a[i],mod-b[i]);
	a.resize(s);
	return a;
}

vector<long long> solve(long long n, vector<long long> m)
{
	vector<long long> res(m.size()-1);
	if (n < res.size()){
		res[n] = 1;
	}
	else{
		vector<long long> w = m;
		for (int i=w.size()%2;i<w.size();i+=2) w[i] = (mod - w[i]);
		vector<long long> m2 = poly_mul(m,w);
		vector<long long> mp(m.size());
		for (int i=0;i<m.size();i++) mp[i] = m2[i*2];

		vector<long long> c2 = solve(n/2,mp);
		vector<long long> cp(c2.size()*2);
		int p = n & 1;
		for (int i=0;i<c2.size();i++) cp[i*2+p] = c2[i];

		res = poly_div(cp,m);
	}
	return res;
}

int main()
{
	init();

	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);
	
	vector<long long> m(N+2);
	m[N+1] = 1; m[N] = mod - 1;
	for (int i=0;i<N;i++){
		long long u = mul(Q[i],v);
		m[i] = add(m[i],u);
		m[i+1] = add(m[i+1],mod-u);
	}

	vector<long long> coeff = solve(M,m);
	printf ("%lld\n",coeff[N]);

	return 0;
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	25468 KB	Output is correct
2	Correct	37 ms	25468 KB	Output is correct
3	Correct	41 ms	25468 KB	Output is correct
4	Correct	41 ms	25468 KB	Output is correct
5	Correct	37 ms	25468 KB	Output is correct
6	Correct	30 ms	25464 KB	Output is correct
7	Correct	40 ms	25464 KB	Output is correct
8	Correct	37 ms	25472 KB	Output is correct
9	Correct	37 ms	25468 KB	Output is correct
10	Correct	42 ms	25468 KB	Output is correct
11	Correct	41 ms	25472 KB	Output is correct
12	Correct	42 ms	25464 KB	Output is correct
13	Correct	33 ms	25464 KB	Output is correct
14	Correct	34 ms	25472 KB	Output is correct
15	Correct	42 ms	25464 KB	Output is correct
16	Correct	42 ms	25468 KB	Output is correct
17	Correct	41 ms	25468 KB	Output is correct
18	Correct	41 ms	25468 KB	Output is correct
19	Correct	22 ms	25140 KB	Output is correct
20	Correct	22 ms	25140 KB	Output is correct
21	Correct	42 ms	25496 KB	Output is correct
22	Correct	42 ms	25496 KB	Output is correct
23	Correct	42 ms	25496 KB	Output is correct
24	Correct	45 ms	25496 KB	Output is correct
25	Correct	35 ms	25496 KB	Output is correct
26	Correct	29 ms	25272 KB	Output is correct
27	Correct	35 ms	25272 KB	Output is correct
28	Correct	28 ms	25272 KB	Output is correct
29	Correct	32 ms	25272 KB	Output is correct
30	Correct	35 ms	25272 KB	Output is correct

Subtask #2

96.0 / 96.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3114 ms	49320 KB	Output is correct
2	Correct	2850 ms	46884 KB	Output is correct
3	Correct	3134 ms	49288 KB	Output is correct
4	Correct	3049 ms	48544 KB	Output is correct
5	Correct	3015 ms	48524 KB	Output is correct
6	Correct	3036 ms	48896 KB	Output is correct
7	Correct	3042 ms	48408 KB	Output is correct
8	Correct	3137 ms	49300 KB	Output is correct
9	Correct	2887 ms	47776 KB	Output is correct
10	Correct	3032 ms	48524 KB	Output is correct
11	Correct	2788 ms	42748 KB	Output is correct
12	Correct	2936 ms	43068 KB	Output is correct
13	Correct	3083 ms	43580 KB	Output is correct
14	Correct	3195 ms	44092 KB	Output is correct
15	Correct	2416 ms	43068 KB	Output is correct
16	Correct	1654 ms	41780 KB	Output is correct
17	Correct	1500 ms	38220 KB	Output is correct
18	Correct	1477 ms	37192 KB	Output is correct
19	Correct	1504 ms	37188 KB	Output is correct
20	Correct	1534 ms	37188 KB	Output is correct