| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 33930 |
2017-11-05T08:54:19 Z |
gs14004 |
목공 (kriii4_A) |
C++14 |
|
1689 ms |
4656 KB |
#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
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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
2404 KB |
Output is correct |
| 2 |
Correct |
26 ms |
2408 KB |
Output is correct |
| 3 |
Correct |
26 ms |
2408 KB |
Output is correct |
| 4 |
Correct |
26 ms |
2404 KB |
Output is correct |
| 5 |
Correct |
26 ms |
2408 KB |
Output is correct |
| 6 |
Correct |
26 ms |
2412 KB |
Output is correct |
| 7 |
Correct |
26 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
23 ms |
2404 KB |
Output is correct |
| 9 |
Correct |
23 ms |
2408 KB |
Output is correct |
| 10 |
Correct |
23 ms |
2404 KB |
Output is correct |
| 11 |
Correct |
26 ms |
2404 KB |
Output is correct |
| 12 |
Correct |
23 ms |
2412 KB |
Output is correct |
| 13 |
Correct |
23 ms |
2408 KB |
Output is correct |
| 14 |
Correct |
26 ms |
2408 KB |
Output is correct |
| 15 |
Correct |
29 ms |
2408 KB |
Output is correct |
| 16 |
Correct |
23 ms |
2404 KB |
Output is correct |
| 17 |
Correct |
23 ms |
2408 KB |
Output is correct |
| 18 |
Correct |
23 ms |
2404 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2404 KB |
Output is correct |
| 20 |
Correct |
0 ms |
2408 KB |
Output is correct |
| 21 |
Correct |
26 ms |
2420 KB |
Output is correct |
| 22 |
Correct |
23 ms |
2416 KB |
Output is correct |
| 23 |
Correct |
23 ms |
2420 KB |
Output is correct |
| 24 |
Correct |
23 ms |
2420 KB |
Output is correct |
| 25 |
Correct |
19 ms |
2408 KB |
Output is correct |
| 26 |
Correct |
9 ms |
2408 KB |
Output is correct |
| 27 |
Correct |
13 ms |
2408 KB |
Output is correct |
| 28 |
Correct |
9 ms |
2408 KB |
Output is correct |
| 29 |
Correct |
9 ms |
2404 KB |
Output is correct |
| 30 |
Correct |
9 ms |
2408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1493 ms |
4652 KB |
Output is correct |
| 2 |
Correct |
1479 ms |
4648 KB |
Output is correct |
| 3 |
Correct |
1619 ms |
4616 KB |
Output is correct |
| 4 |
Correct |
1603 ms |
4652 KB |
Output is correct |
| 5 |
Correct |
1579 ms |
4636 KB |
Output is correct |
| 6 |
Correct |
1623 ms |
4644 KB |
Output is correct |
| 7 |
Correct |
1689 ms |
4636 KB |
Output is correct |
| 8 |
Correct |
1586 ms |
4644 KB |
Output is correct |
| 9 |
Correct |
1443 ms |
4656 KB |
Output is correct |
| 10 |
Correct |
1493 ms |
4636 KB |
Output is correct |
| 11 |
Correct |
1369 ms |
4408 KB |
Output is correct |
| 12 |
Correct |
1429 ms |
4408 KB |
Output is correct |
| 13 |
Correct |
1603 ms |
4412 KB |
Output is correct |
| 14 |
Correct |
1626 ms |
4412 KB |
Output is correct |
| 15 |
Correct |
1249 ms |
4276 KB |
Output is correct |
| 16 |
Correct |
746 ms |
3636 KB |
Output is correct |
| 17 |
Correct |
783 ms |
3512 KB |
Output is correct |
| 18 |
Correct |
749 ms |
3508 KB |
Output is correct |
| 19 |
Correct |
776 ms |
3508 KB |
Output is correct |
| 20 |
Correct |
746 ms |
3512 KB |
Output is correct |
