Submission #2628363
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(var,n) for(int var=0;var<(n);++var)
#define rep1(var,n) for(int var=1;var<=(n);++var)
#define DEFAULT_MOD 1000000007LL
template<class T>
T extgcd(T a, T b, T& x, T& y) {
for (T u=y=1,v=x=0; a; ) {
T q = b / a;
swap(x -= q*u, u);
swap(y -= q*v, v);
swap(b -= q*a, a);
}
return b;
}
inline long long mod_pow(long long x, long long e, long long mod) {
long long v = 1LL;
for ( ; e; e>>=1) {
if (e & 1) v = (v * x) % mod;
x = (x * x) % mod;
}
return v;
}
inline long long mod_inv_naive(long long a, long long mod) {
return mod_pow(a, mod-2, mod);
}
inline long long mod_inv_extgcd(long long a, long long mod) {
long long x, y;
extgcd(a, mod, x, y);
return (mod + x % mod) % mod;
// ax + MODy = 1
// x = (1 - MODy)/a = 1/a - MODy/a
}
//#define mod_inv mod_inv_naive
#define mod_inv mod_inv_extgcd
class mint {
public:
long long val;
long long mod;
long long _inv;
public:
mint()
: val(0), mod(DEFAULT_MOD), _inv(0) {
// fprintf(stderr, "mint()\n");
}
mint(const mint& m)
: val(m.val), mod(m.mod), _inv(m._inv) {
// fprintf(stderr, "mint(m<val=%lld,mod=%lld,_inv=%lld>)\n", val,mod,_inv);
}
mint(long long v, long long mod=DEFAULT_MOD, long long inv=0)
: val((v % mod + mod) % mod), mod(mod), _inv(inv) {
// fprintf(stderr, "mint(v=%lld, mod=%lld, inv=%lld) -> %lld\n", v,mod,_inv, val);
}
#ifdef DEBUG
std::string desc() {
std::stringstream ss;
ss << "<" << val << "(mod " << mod << "),inv=" << inv().val << ">";
return ss.str();
}
#endif
mint& set(long long newval) {
val = (newval % mod + mod) % mod;
_inv = 0;
return *this;
}
mint& set(mint& b) { // *this = b; return *this;
val = b.val;
mod = b.mod;
_inv = b._inv;
return *this;
}
mint operator+(mint b){ return mint(this->val + b.val, mod); }
mint operator+(long long v){ return mint(this->val + v, mod); }
mint& operator+=(mint b){ return set(this->val + b.val); }
mint& operator+=(long long v){ return set(this->val + v); }
mint operator-(mint b){ return mint(this->val - b.val, mod); }
mint operator-(long long v){ return mint(this->val - v, mod); }
mint& operator-=(mint b){ return set(this->val - b.val); }
mint& operator-=(long long v){ return set(this->val - v); }
mint operator*(mint b){ return mint(this->val * b.val, mod); }
mint operator*(long long v){ return mint(this->val * v, mod); }
mint& operator*=(mint b){ return set(this->val * b.val); }
mint& operator*=(long long v){ return set(this->val * v); }
mint operator-(){ return mint(-this->val, mod); }
bool operator==(mint b){ return this->val == b.val; }
bool operator==(long long v){ return this->val == ((v + mod) % mod); }
bool operator!=(mint b){ return this->val != b.val; }
bool operator!=(long long v){ return this->val != ((v + mod) % mod); }
// pow
mint operator^(long long e){ return mint(mod_pow(this->val, e, mod), mod); }
mint& operator^=(long long e) { return set(mod_pow(this->val, e, mod)); }
mint inv() {
if (_inv == 0) _inv = mod_inv(this->val, mod);
return mint(_inv, mod);
}
// div
mint operator/(mint b){ return mint(this->val * b.inv().val, mod); }
mint operator/(long long b){ return mint(this->val * mod_inv(b, mod), mod); }
mint& operator/=(mint b){ return set(this->val * b.inv().val); }
mint& operator/=(long long b){ return set(this->val * mod_inv(b, mod)); }
};
std::ostream& operator<<(std::ostream& os, const mint& m){ return ( os << m.val ); }
template <long long MOD>
class Mint : public mint {
public:
Mint(): mint(0, MOD) {}
Mint(long long v): mint(v, MOD) {}
};
// #include "ntt.h"
mint garner(vector<mint>& mr, long long mod) {
int M = mr.size();
mr.push_back(mint(0, mod));
vector<mint> coeffs(M+1), constants(M+1);
for (int i=0; i<M+1; ++i) {
coeffs[i] = mint(1, mr[i].mod);
constants[i] = mint(0, mr[i].mod);
}
for (int i=0; i<M; ++i) {
// coffs[i] * v + constants[i] == mr[i].val (mod mr[i].first) を解く
mint v(mr[i] - constants[i]);
v /= coeffs[i];
for (int j=i+1; j<M+1; j++) {
constants[j] += coeffs[j] * v.val;
coeffs[j] *= mr[i].mod;
}
}
mr.pop_back();
return constants.back();
}
template<typename T>
inline void bit_reverse(vector<T>& a) {
int n = a.size();
int i = 0;
for (int j=1; j<n-1; ++j) {
for (int k = n >> 1; k >(i ^= k); k >>= 1);
if (j < i) swap(a[i], a[j]);
}
}
template<long long mod, long long primitive_root>
class NTT {
public:
void _ntt(vector<mint>& a, int sign) {
assert(a[0].mod == mod);
const int n = a.size();
assert((n ^ (n&-n)) == 0); //n = 2^k
const long long g = 3; // g is primitive root of mod
mint tmp = mint(-1, mod) / n; // tmp = -1/n
mint h = mint(g, mod) ^ tmp.val; // h = ^n√3
if (sign == -1) h = h.inv();
bit_reverse(a);
for (int m=1; m<n; m<<=1) {
const int m2 = 2 * m;
// const ll base = mod_pow(h, n / m2, mod);
// mint base = h ^ (n/m2);
// mint w(1, mod);
long long base = mod_pow(h.val, n/m2, mod);
long long w = 1;
for(int x=0; x<m; ++x) {
for (int s=x; s<n; s+=m2) {
// mint u = a[s];
// mint d = a[s + m] * w;
// a[s] = u + d;
// a[s + m] = u - d;
long long u = a[s].val;
long long d = (a[s + m].val * w) % mod;
a[s].val = (u + d) % mod;
a[s + m].val = (u - d + mod) % mod;
a[s]._inv = a[s + m]._inv = 0;
}
// w *= base;
w = (w * base) % mod;
}
}
}
void ntt(vector<mint>& input) {
_ntt(input, 1);
}
void intt(vector<mint>& input) {
_ntt(input, -1);
// mint n(input.size(), mod);
// for (auto &x : input) x *= n.inv(); // = x * n_inv % mod;
const long long n_inv = mod_inv(input.size(), mod);
for (auto &x : input) x *= n_inv;
}
// 畳み込み演算を行う
vector<mint> convolution(const vector<long long>& a, const vector<long long>& b){
int result_size = a.size() + b.size() - 1;
// int n = pow_2_at_least(result_size);
int n = 1; while (n < result_size) n <<= 1;
vector<mint> _a(n, mint(0,mod)), _b(n, mint(0,mod));
for (int i=0; i<a.size(); ++i) _a[i].val = a[i];
for (int i=0; i<b.size(); ++i) _b[i].val = b[i];
ntt(_a);
ntt(_b);
for (int i=0; i<n; ++i) _a[i] *= _b[i];
intt(_a);
_a.resize(result_size);
return _a;
}
};
vector<long long> convolution_ntt_mod(vector<long long>& a, vector<long long>& b, int mod) {
for (auto &x : a) x %= mod;
for (auto &x : b) x %= mod;
if (mod < 1224736769) {
NTT<1224736769, 3> ntt3;
vector<mint> x3 = ntt3.convolution(a, b);
vector<long long> ret(x3.size());
for (int i=0,c=x3.size(); i<c; ++i) {
ret[i] = x3[i].val;
}
return ret;
}
NTT<167772161, 3> ntt1;
NTT<469762049, 3> ntt2;
NTT<1224736769, 3> ntt3;
vector<vector<mint>> xs(3);
xs[0] = ntt1.convolution(a, b);
xs[1] = ntt2.convolution(a, b);
xs[2] = ntt3.convolution(a, b);
vector<mint> mr { xs[0][0], xs[1][0], xs[2][0] };
vector<long long> ret(xs[0].size());
for (int i=0,c=xs[0].size(); i<c; ++i) {
mr[0].set(xs[0][i].val);
mr[1].set(xs[1][i].val);
mr[2].set(xs[2][i].val);
ret[i] = garner(mr, mod).val;
}
return ret;
}
int main() {
int N; cin >> N; // 1-100000
vector<ll> g(N+1), h(N+1);
g[0] = h[0] = 0;
rep(i,N){
int A,B; cin >> A >> B;
g[1+i] = A;
h[1+i] = B;
}
vector<ll> f = convolution_ntt_mod(g, h, 1000000007LL);
rep1(k, N*2){
cout << f[k] << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 高速フーリエ変換 |
User |
naoya_t |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
7955 Byte |
Status |
AC |
Exec Time |
454 ms |
Memory |
14080 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_01 |
All |
00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_01 |
AC |
1 ms |
256 KB |
01_00_01 |
AC |
1 ms |
256 KB |
01_01_19 |
AC |
1 ms |
256 KB |
01_02_31 |
AC |
1 ms |
256 KB |
01_03_22 |
AC |
1 ms |
256 KB |
01_04_31 |
AC |
1 ms |
256 KB |
01_05_40 |
AC |
1 ms |
256 KB |
01_06_15 |
AC |
1 ms |
256 KB |
01_07_39 |
AC |
1 ms |
256 KB |
01_08_28 |
AC |
1 ms |
256 KB |
01_09_30 |
AC |
1 ms |
256 KB |
01_10_23 |
AC |
1 ms |
256 KB |
01_11_33 |
AC |
1 ms |
256 KB |
01_12_11 |
AC |
1 ms |
256 KB |
01_13_28 |
AC |
1 ms |
256 KB |
01_14_41 |
AC |
1 ms |
256 KB |
01_15_26 |
AC |
1 ms |
256 KB |
01_16_49 |
AC |
1 ms |
256 KB |
01_17_34 |
AC |
1 ms |
256 KB |
01_18_02 |
AC |
1 ms |
256 KB |
01_19_33 |
AC |
1 ms |
256 KB |
01_20_29 |
AC |
1 ms |
256 KB |
02_00_51254 |
AC |
229 ms |
7168 KB |
02_01_82431 |
AC |
393 ms |
13824 KB |
02_02_17056 |
AC |
84 ms |
3584 KB |
02_03_34866 |
AC |
176 ms |
6912 KB |
02_04_6779 |
AC |
29 ms |
1152 KB |
02_05_65534 |
AC |
277 ms |
7424 KB |
02_06_65535 |
AC |
277 ms |
7424 KB |
02_07_65536 |
AC |
335 ms |
13568 KB |
02_08_65537 |
AC |
333 ms |
13568 KB |
02_09_65538 |
AC |
335 ms |
13568 KB |
02_10_100000 |
AC |
454 ms |
14080 KB |