結果
問題 | No.754 畳み込みの和 |
ユーザー |
|
提出日時 | 2021-08-26 18:33:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 5,000 ms |
コード長 | 1,801 bytes |
コンパイル時間 | 3,620 ms |
コンパイル使用メモリ | 236,228 KB |
最終ジャッジ日時 | 2025-01-24 02:04:00 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/modint>#include<atcoder/convolution>using namespace atcoder;using mint = modint1000000007;using namespace std;using ll = long long;using P = pair<ll,ll>;ll exgcd(ll a,ll b,ll &x,ll &y){x=0, y=1; ll u=1, v=0;while(a){ll t{b/a};swap(b-=t*a, a);swap(x-=t*u, u);swap(y-=t*v, v);}if(b<0) b*=-1, x*=-1, y*=-1;return b;}ll inv(ll a, ll MOD){ll x{0},y{1};exgcd(a,MOD,x,y);return (x%MOD+MOD)%MOD;}ll garner(vector<ll>&b,vector<ll>&m){int sz = m.size();vector<ll> coef(sz,1), cons(sz,0);for(int k=0; k<(int)b.size(); k++){ll t = (b[k]-cons[k]);t *= inv(coef[k],m[k]);t = ( (t%m[k]) + m[k] ) % m[k];for(int i=k+1; i<sz; i++){(cons[i] += t*coef[i] ) %= m[i];(coef[i] *= m[k]) %= m[i];}}return cons.back();}vector<mint> mod_conv(vector<mint>a,vector<mint>b){int MOD = mint::mod();const int nhg2 = 167772161;const int nhg3 = 469762049;const int nhg4 = 1224736769;vector<ll>c(a.size()),d(b.size());for(int i=0; i<(int)a.size(); i++){c[i] = a[i].val();}for(int i=0; i<(int)b.size(); i++){d[i] = b[i].val();}auto x = convolution<nhg2>(c,d);auto y = convolution<nhg3>(c,d);auto z = convolution<nhg4>(c,d);int n = x.size();vector<mint> ret(n);vector<ll> f {nhg2,nhg3,nhg4,MOD};for(int i=0; i<n; i++){vector<ll> e {x[i],y[i],z[i]};ret[i] = garner(e,f);}return ret;}int main(){int n; cin>>n;vector<mint>a(n+1),b(n+1);for(int i=0; i<=n; i++){int t; cin>>t;a[i] = t;}for(int i=0; i<=n; i++){int t; cin>>t;b[i] = t;}auto c = mod_conv(a,b);mint ans{};for(int i=0; i<=n; i++){ans += c[i];}cout<<ans.val()<<endl;}