Submission #19046

#	Time	Username	Problem	Language	Result	Execution time	Memory
19046		kriii	목공 (kriii4_A)	C++14	100 / 100	3195 ms	49320 KiB

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 / 4
• Subtask 2: 96 / 96