| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 19045 | kriii | 목공 (kriii4_A) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#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;
}