結果

問題 No.754 畳み込みの和
コンテスト
ユーザー hashiryo
提出日時 2019-07-09 15:36:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 228 ms / 5,000 ms
コード長 4,515 bytes
コンパイル時間 2,134 ms
コンパイル使用メモリ 181,564 KB
実行使用メモリ 18,732 KB
最終ジャッジ日時 2024-10-12 05:25:18
合計ジャッジ時間 4,094 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/2;
const ll MOD = 1e9+7;
const double EPS=1e-12;


typedef long long ll;
ll add(ll a, ll b, ll M) { // a + b (mod M)
    return (a += b) >= M ? a - M : a;
}
ll sub(ll a, ll b, ll M) { // a - b (mod M)
    return (a -= b) < 0 ? a + M : a;
}
ll mul(ll a, ll b, ll M) { // a * b (mod M)
    ll r = a*b - (ll)((long double)(a)*b/M+.5)*M;
    return r < 0 ? r + M: r;
}
ll div(ll a, ll b, ll M) { // solve b x == a (mod M)
    ll u = 1, x = 0, s = b, t = M;
    while (s) { // extgcd for b x + M s = t
        ll q = t / s;
        swap(x -= u * q, u);
        swap(t -= s * q, s);
    }
    if (a % t) return -1; // infeasible
    return mul(x < 0 ? x + M : x, a / t, M); // b (xa/t) == a (mod M)
}
ll pow(ll a, ll b, ll M) {
    ll x = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) x = (a * x) % M;
        a = (a * a) % M;
    }
    return x;
}

// p(x) = p[0] + p[1] x + ... + p[n-1] x^n-1
// assertion: p.back() != 0
typedef vector<ll> poly;
ostream& operator<<(ostream &os, const poly &p) {
    bool head = true;
    for (size_t i = 0; i < p.size(); ++i) {
        if (p[i] == 0) continue;
        if (!head) os << " + ";
        os << p[i];
        head = false;
        if (i >= 1) os << " x";
        if (i >= 2) os << "^" << i;
    }
    return os;
}
poly add(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = add(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}
poly sub(poly p, const poly &q, ll M) {
    if (p.size() < q.size()) p.resize(q.size());
    for (size_t i = 0; i < q.size(); ++i)
        p[i] = sub(p[i], q[i], M);
    while (!p.empty() && !p.back()) p.pop_back();
    return p;
}

// FFT-based multiplication: this works correctly for M in [int]
// assume: size of a/b is power of two, mod is predetermined
template <int mod, int sign>
void fmt(vector<ll>& x) {
    const int n = x.size();
    int h = pow(3, (mod-1)/n, mod);
    if (sign < 0) h = div(1, h, mod);
    for (int i = 0, j = 1; j < n-1; ++j) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1);
        if (j < i) swap(x[i], x[j]);
    }
    for (int m = 1; m < n; m *= 2) {
        ll w = 1, wk = pow(h, n / (2*m), mod);
        for (int i = 0; i < m; ++i) {
            for (int s = i; s < n; s += 2*m) {
                ll u = x[s], d = x[s + m] * w % mod;
                if ((x[s] = u + d) >= mod) x[s] -= mod;
                if ((x[s + m] = u - d) < 0) x[s + m] += mod;
            }
            w = w * wk % mod;
        }
    }
    if (sign < 0) {
        ll inv = div(1, n, mod);
        for (auto &a: x)
            a = a * inv % mod;
    }
}
// assume: size of a/b is power of two, mod is predetermined
template <int mod>
vector<ll> conv(vector<ll> a, vector<ll> b){
    fmt<mod,+1>(a); fmt<mod,+1>(b);
    for (size_t i = 0; i < a.size(); ++i)
        a[i] = a[i] * b[i] % mod;
    fmt<mod,-1>(a);
    return a;
}
// general convolution where mod < 2^31.
inline vector<ll> conv(vector<ll> a, vector<ll> b, ll mod){
    int n = a.size() + b.size() - 1;
    for (int k: {1,2,4,8,16}) n |= (n >> k);
    ++n;
    a.resize(n); b.resize(n);
    const int A = 167772161, B = 469762049, C = 1224736769, D = (ll)(A) * B % mod;
    if(mod==A)return conv<A>(a,b);
    if(mod==B)return conv<B>(a,b);
    if(mod==C)return conv<C>(a,b);
    vector<ll> x = conv<A>(a,b), y = conv<B>(a,b), z = conv<C>(a,b);
    for (size_t i = 0; i < x.size(); ++i) {
        ll X = (y[i] - x[i]) * 104391568;
        if ((X %= B) < 0) X += B;
        ll Y = (z[i] - (x[i] + A * X) % C) * 721017874;
        if ((Y %= C) < 0) Y += C;
        x[i] += A * X + D * Y;
        if ((x[i] %= mod) < 0) x[i] += mod;
    }
    x.resize(n);
    return x;
}
poly mul(poly p, poly q, ll M) {
    poly pq = conv(p, q, M);
    pq.resize(p.size() + q.size() - 1);
    while (!pq.empty() && !pq.back()) pq.pop_back();
    return pq;
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;cin>>N;
  poly a(N+1),b(N+1);
  for(ll i=0;i<=N;i++)cin>>a[i];
  for(ll i=0;i<=N;i++)cin>>b[i];
  poly c=mul(a,b,MOD);
  ll ans=0;
  for(ll i=0;i<=N;i++)ans=add(ans,c[i],MOD);
  cout<<ans<<endl;
  return 0;
}
0