Submission #33930

#	Time	Username	Problem	Language	Result	Execution time	Memory
33930		gs14004	목공 (kriii4_A)	C++14	100 / 100	1689 ms	4656 KiB

A

#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1092616193;
const int prr = 3;
const int MAXN = 16005;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

void fft(vector<lint> &a, bool inv){
	int n = a.size(), j = 0;
	vector<lint> roots(n/2);
	for(int i=1; i<n; i++){
		int bit = (n >> 1);
		while(j >= bit){
			j -= bit;
			bit >>= 1;
		}
		j += bit;
		if(i < j) swap(a[i], a[j]);
	}
	int ang = ipow(prr, (mod - 1) / n);
	if(inv) ang = ipow(ang, mod - 2);
	for(int i=0; i<n/2; i++){
		roots[i] = (i ? (1ll * roots[i-1] * ang % mod) : 1);
	}
	for(int i=2; i<=n; i<<=1){
		int step = n / i;
		for(int j=0; j<n; j+=i){
			for(int k=0; k<i/2; k++){
				lint u = a[j+k], v = a[j+k+i/2] * roots[step * k] % mod;
				a[j+k] = (u+v)%mod;
				a[j+k+i/2] = (u-v+mod)%mod;
			}
		}
	}
	if(inv) for(int i=0; i<n; i++) a[i] = (a[i] * ipow(n, mod - 2) % mod);
}


vector<lint> multiply(vector<lint> &v, vector<lint> &w){
	vector<lint> fv(v.begin(), v.end()), fw(w.begin(), w.end());
	int n = 2;
	while(n < v.size() + w.size()) n <<= 1;
	fv.resize(n);
	fw.resize(n);
	fft(fv, 0);
	fft(fw, 0);
	for(int i=0; i<n; i++) fv[i] = 1ll * fv[i] * fw[i] % mod;
	fft(fv, 1);
	vector<lint> ret(n);
	for(int i=0; i<n; i++) ret[i] = fv[i];
	return ret;
}

vector<lint> rbi, dv;

vector<lint> get_inv(int n, const vector<lint> &p){
	vector<lint> q = {ipow(p[0], mod - 2)};
	for(int i=2; i<=n; i<<=1){
		vector<lint> res;
		vector<lint> fq(q.begin(), q.end()); fq.resize(2*i);
		vector<lint> fp(p.begin(), p.begin() + i); fp.resize(2*i);
		fft(fq, 0);
		fft(fp, 0);
		for(int j=0; j<2*i; j++){
			fp[j] *= fq[j] * fq[j] % mod;
			fp[j] %= mod;
		}
		fft(fp, 1);
		res.resize(i);
		for(int j=0; j<i; j++){
			res[j] = mod - fp[j];
			if(j < i/2) res[j] += 2 * q[j];
			res[j] %= mod;
		}
		q = res;
	}
	return q;
}

vector<lint> poly_divide(const vector<lint> &a, const vector<lint> &b){
	int n = a.size(), m = b.size();
	int k = 2; while(k < n-m+1) k <<= 1; 
	vector<lint> ra(k);
	for(int i=0; i<n && i<k; ++i) ra[i] = a[n-i-1];
	vector<lint> res = multiply(rbi, ra);
	res.resize(n - m + 1);
	reverse(res.begin(), res.end());
	return res;
}

int n;
lint m, a[MAXN], b[MAXN];

vector<lint> solve(lint x){
	if(x == 0){
		vector<lint> ret(n);
		ret[0] = 1;
		return ret;
	}
	if(x & 1){
		vector<lint> cf = solve(x - 1);
		vector<lint> ret(n);
		for(int i=0; i+1<n; i++){
			ret[i+1] = cf[i];
		}
		for(int i=0; i<n; i++){
			ret[i] += cf[n-1] * b[n-i];
			ret[i] %= mod;
		}
		return ret;
	}
	vector<lint> cf = solve(x / 2);
	vector<lint> ret = multiply(cf, cf);
	ret.resize(2*n-1);
	auto mok = poly_divide(ret, dv);
	mok = multiply(mok, dv);
	for(int i=0; i<n; i++){
		ret[i] += mod - mok[i];
		ret[i] %= mod;
	}
	ret.resize(n);
	return ret;
}

int main(){
	cin >> n >> m;
	int sum = 0;
	lint tb[MAXN] = {};
	for(int i=n; i; i--){
		scanf("%lld",&tb[i]);
		sum += tb[i];
	}
	a[n++] = 1;
	b[1] += 1;
	for(int i=1; i<n; i++) b[i] += tb[i] * ipow(sum, mod - 2) % mod;
	for(int i=2; i<=n; i++) b[i] += mod - tb[i-1] * ipow(sum, mod - 2) % mod;
	for(int i=1; i<=n; i++) b[i] %= mod;
	dv.resize(n + 1);
	for(int i=0; i<n; i++) dv[i] = (mod - b[n-i]) % mod;
	dv[n] = 1;
	int k = 2;
	while(k < n - 1) k <<= 1;
	vector<lint> rb(k);
	for(int i=0; i<n+1 && i<k; i++) rb[i] = dv[n-i];
	rbi = get_inv(k, rb);
	auto x = solve(m);
	lint ans = 0;
	for(int i=0; i<n; i++) ans += a[i] * x[i] % mod;
	cout << ans % mod << endl;
}

Compilation message (stderr)

A.cpp: In function 'std::vector<long long int> multiply(std::vector<long long int>&, std::vector<long long int>&)':
A.cpp:56:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(n < v.size() + w.size()) n <<= 1;
          ^
A.cpp: In function 'int main()':
A.cpp:144:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&tb[i]);
                       ^

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