結果
問題 | No.754 畳み込みの和 |
ユーザー | soraie_ |
提出日時 | 2021-03-20 10:26:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 872 ms / 5,000 ms |
コード長 | 14,487 bytes |
コンパイル時間 | 5,029 ms |
コンパイル使用メモリ | 273,084 KB |
実行使用メモリ | 21,868 KB |
最終ジャッジ日時 | 2024-11-20 19:24:31 |
合計ジャッジ時間 | 8,980 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 868 ms
21,864 KB |
testcase_01 | AC | 868 ms
21,868 KB |
testcase_02 | AC | 872 ms
21,740 KB |
ソースコード
#ifdef _DEBUG #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; //-------------------------------------------------------------------- #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define overload4(_1,_2,_3,_4,name,...) name #define rep1(n) for(ll _=0;_<(ll)n;++_) #define rep2(i,n) for(ll i=0;i<(ll)n;++i) #define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i) #define rep4(i,a,b,c) for(ll i=(ll)a;i<(ll)b;i+=(ll)c) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #ifdef _DEBUG #define pass(...) __VA_ARGS__ ; #define debug1(a) cerr<<#a<<": "<<a<<"\n" #define debug2(a,b) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cerr<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" /* #define debug1(a) cout<<#a<<": "<<a<<"\n" #define debug2(a,b) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<"\n" #define debug3(a,b,c) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<"\n" #define debug4(a,b,c,d) cout<<#a<<": "<<a<<", "<<#b<<": "<<b<<", "<<#c<<": "<<c<<", "<<#d<<": "<<d<<"\n" */ #define debug(...) overload4(__VA_ARGS__,debug4,debug3,debug2,debug1)(__VA_ARGS__) #define koko cerr << "koko\n"; #else #define debug(...) void(0) #define pass(...) void(0); #define koko void(0); #endif #define mp make_pair //#define fi first //#define se second void myset(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} void doset(int n){cout << fixed << setprecision(n);cerr << fixed << setprecision(n);} using ll = long long; using ld = long double; using dou = double; template<class First,class Second>ostream& operator<<(ostream& os,const pair<First,Second>& pp) {return os << "{" << pp.first << "," << pp.second << "}";} template<class T>ostream& operator<<(ostream& os,const vector<T>& VV) {if(VV.empty())return os<<"[]";os<<"[";rep(i,VV.size())os<<VV[i]<<(i==int(VV.size()-1)?"]":",");return os;} template<class T>ostream& operator<<(ostream& os,const set<T>& SS) {if(SS.empty())return os<<"[]";os<<"[";auto ii=SS.begin();for(;ii!=SS.end();ii++)os<<*ii<<(ii==prev(SS.end())?"]":",");return os;} template<class Key,class Tp>ostream& operator<<(ostream& os,const map<Key,Tp>& MM) {if(MM.empty())return os<<"[]";os<<"[";auto ii=MM.begin();for(;ii!=MM.end();ii++)os<<"{"<<ii->first<<":"<<ii->second<<"}"<<(ii==prev(MM.end())?"]":",");return os;} const int inf = 1 << 30; const ll INF = 1LL << 61; const ld pi = 3.14159265358; const ll mod1 = 1000000007LL; const ll mod2 = 998244353LL; typedef pair<ll,ll> P; template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; } template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } ll modpow(ll n,ll m,ll MOD){ if(m == 0)return 1; if(m < 0)return 0; ll res = 1; n %= MOD; while(m){ if(m & 1)res = (res * n) % MOD; m >>= 1; n *= n; n %= MOD; } return res; } ll mypow(ll n,ll m){ if(m == 0)return 1; if(m < 0)return -1; ll res = 1; while(m){ if(m & 1)res = (res * n); m >>= 1; n *= n; } return res; } inline bool isp(ll n){ bool res = true; if(n == 1 || n == 0)return false; else{ for(ll i = 2;i * i <= n;i++){ if(n % i == 0){ res = false; break; } } return res; } } inline bool Yes(bool b = 1){cout << (b ? "Yes\n":"No\n");return b;} inline bool YES(bool b = 1){cout << (b ? "YES\n":"NO\n");return b;} map<ll,ll> primefactor(ll n){ map<ll,ll> ma; if(n <= 1)return ma; ll m = n; for(ll i = 2;i * i <= n;i++){ while(m % i == 0){ ma[i]++; m /= i; } } if(m != 1)ma[m]++; return ma; } vector<ll> divisor(ll n,bool sorted = true,bool samein = false){ vector<ll> res; for(ll i = 1;i * i <= n;i++){ if(n % i == 0){ res.push_back(i); if(i * i != n || samein)res.push_back(n / i); } } if(sorted)sort(all(res)); return res; } ll __lcm(ll a,ll b){return a / __gcd(a,b) * b;} template<class T>T sum(const vector<T> &V){T r=0;for(auto x:V)r+=x;return r;} template<class T>T sum(const initializer_list<T> &V){T r=0;for(auto x:V)r+=x;return r;} //#include <atcoder/all> //#include "atcoder/lazysegtree.hpp" //using namespace atcoder; //-------------------------------------------------------------------- long long extgcd(long long a,long long b,long long &x,long long &y){ if(b == 0){ x = 1; y = 0; return a; } long long d = extgcd(b,a % b,y,x); y -= a / b * x; return d; } long long modinv(long long a,long long p){ long long b = p, u = 1, v = 0; while(b){ long long t = a / b; a -= t * b;std::swap(a, b); u -= t * v;std::swap(u, v); } u %= p; if(u < 0)u += p; return u; } /** * @brief garner precalc * @return long long */ long long pregarner(std::vector<long long> &rems,std::vector<long long> &mods,long long MOD){ assert(rems.size() == mods.size()); for(int i = 0;i < int(rems.size());i++){ for(int j = 0;j < i;j++){ long long g = std::gcd(mods[i],mods[j]); if((rems[i] - rems[j]) % g != 0)return -1; mods[i] /= g;mods[j] /= g; long long gi = std::gcd(g,mods[i]),gj = g / gi; do{ g = std::gcd(gi,gj); gi *= g;gj /= g; }while(g != 1); mods[i] *= gi;mods[j] *= gj; rems[i] %= mods[i];rems[j] %= mods[j]; } } long long res = 1; for(long long &a : mods)res = res * a % MOD; return res; } /** * @brief returns a integer where rems[i](mod.mods[i]). * @return long long */ long long garner(std::vector<long long> rems,std::vector<long long> mods,long long MOD){ assert(rems.size() == mods.size()); mods.push_back(MOD); int sz = mods.size(); std::vector<long long> cof(sz,1LL),con(sz,0LL); for(int i = 0;i < sz - 1;i++){ long long cur = (rems[i] - con[i]) * modinv(cof[i],mods[i]) % mods[i]; if(cur < 0)cur += mods[i]; for(int j = i + 1;j < sz;j++){ con[j] = (con[j] + cur * cof[j]) % mods[j]; cof[j] = cof[j] * mods[i] % mods[j]; } } return con.back(); } template<long long MOD = 1000000007> struct modint { using mint = modint<MOD>; long long x; modint(long long a = 0):x((a % MOD + MOD) % MOD){} inline constexpr modint operator-()const noexcept{return modint(-x);} inline constexpr modint &operator+=(const modint &a)noexcept{ if ((x += a.x) >= MOD) x -= MOD; return *this; } inline constexpr modint &operator-=(const modint &a)noexcept{ if ((x -= a.x) < 0) x += MOD; return *this; } inline constexpr modint &operator*=(const modint &a)noexcept{ (x *= a.x) %= MOD; return *this; } inline constexpr modint &operator++()noexcept{ x++; if(x == MOD)x = 0; return *this; } inline constexpr modint operator++(int)noexcept{ modint res(*this); operator++(); return res; } inline constexpr modint &operator--()noexcept{ x--; if(x == -1)x = MOD - 1; return *this; } inline constexpr modint operator--(int)noexcept{ modint res(*this); operator--(); return res; } inline constexpr modint operator+(const modint &a)const noexcept{ modint res(*this); return res += a; } inline constexpr modint operator-(const modint &a)const noexcept{ modint res(*this); return res -= a; } inline constexpr modint operator*(const modint &a)const noexcept{ modint res(*this); return res *= a; } inline constexpr modint inv()const{ long long a = x,b = MOD,u = 1,v = 0; while(b){ long long t = a / b; a -= t * b;std::swap(a,b); u -= t * v;std::swap(u,v); } return u; } inline constexpr modint &operator/=(const modint &a)noexcept{return (*this) *= a.inv();} inline constexpr modint operator/(const modint &a)const noexcept{ modint res(*this); return res /= a; } inline constexpr bool operator==(const modint &a)const noexcept{return x == a.x;} friend std::istream &operator>>(std::istream &is,modint &a) { is >> a.x; a.x = (a.x % MOD + MOD) % MOD; return is; } friend std::ostream &operator<<(std::ostream &os,const modint &a){ os << a.x; return os; } long long getmod(){return MOD;} friend mint modpow(mint a,long long b)noexcept{ mint res(1); while(b){ if(b & 1)res *= a; a *= a; b >>= 1; } return res; } }; //using mint = modint<1'000'000'007>::mint; //ex. (2013265921,137,27),(998244353,31,23),(469762049,30,26) template<long long MOD,int base,int max_exp> struct NTT_primitive{ using mint = modint<MOD>; std::vector<mint> bases,invs; NTT_primitive(){ bases.resize(max_exp + 1);invs.resize(max_exp + 1); bases[max_exp] = base; invs[max_exp] = mint(base).inv(); for(int i = max_exp - 1;i >= 0;i--){ bases[i] = bases[i + 1] * bases[i + 1]; invs[i] = invs[i + 1] * invs[i + 1]; } } void dft(std::vector<mint>& vec,int t){ int sz = vec.size(); if(sz == 1)return; std::vector<mint> veca,vecb; for(int i = 0;i < sz / 2;i++){ veca.push_back(vec[i * 2]); vecb.push_back(vec[i * 2 + 1]); } dft(veca,t); dft(vecb,t); int e = __builtin_ffsll(sz) - 1; mint now = 1,zeta = (t == 1 ? bases[e]:invs[e]); for(int i = 0;i < sz;i++){ vec[i] = veca[i % (sz / 2)] + now * vecb[i % (sz / 2)]; now *= zeta; } } std::vector<mint> convolution(const std::vector<mint>& A,const std::vector<mint>& B){ assert(A.size() == B.size()); int sz = 1; while(sz < int(A.size() + B.size()))sz <<= 1; std::vector<mint> f(sz),g(sz); for(int i = 0;i < int(A.size());i++){ f[i] = A[i]; g[i] = B[i]; } dft(f,1);dft(g,1); for(int i = 0;i < sz;i++)f[i] = f[i] * g[i]; dft(f,-1); mint inv = mint(sz).inv(); for(int i = 0;i < sz;i++)f[i] *= inv; return f; } void dft(std::vector<long long>& vec,int t){ int sz = vec.size(); if(sz == 1)return; std::vector<long long> veca,vecb; for(int i = 0;i < sz / 2;i++){ veca.push_back(vec[i * 2]); vecb.push_back(vec[i * 2 + 1]); } dft(veca,t); dft(vecb,t); int e = __builtin_ffsll(sz) - 1; long long now = 1,zeta = (t == 1 ? bases[e].x:invs[e].x); for(int i = 0;i < sz;i++){ vec[i] = (veca[i % (sz / 2)] + now * vecb[i % (sz / 2)] % MOD) % MOD; now = now * zeta % MOD; } } std::vector<long long> convolution(const std::vector<long long>& A,const std::vector<long long>& B){ assert(A.size() == B.size()); int sz = 1; while(sz < int(A.size() + B.size()))sz <<= 1; std::vector<long long> f(sz),g(sz); for(int i = 0;i < int(A.size());i++){ f[i] = A[i] % MOD; g[i] = B[i] % MOD; } dft(f,1);dft(g,1); for(int i = 0;i < sz;i++)f[i] = f[i] * g[i] % MOD; dft(f,-1); long long inv = modinv(sz,MOD); for(int i = 0;i < sz;i++)f[i] = f[i] * inv % MOD; return f; } }; template<long long MOD> struct NTT_all{ NTT_primitive<2013265921,137,27> ntt1; NTT_primitive<998244353,31,23> ntt2; NTT_primitive<469762049,30,26> ntt3; using mint = modint<MOD>; using mint1 = modint<2013265921>; using mint2 = modint<998244353>; using mint3 = modint<469762049>; NTT_all(){} std::vector<mint> convolution(const std::vector<mint>& A,const std::vector<mint>& B){ assert(A.size() == B.size()); int sz = A.size(); std::vector<mint1> A1(sz),B1(sz); std::vector<mint2> A2(sz),B2(sz); std::vector<mint3> A3(sz),B3(sz); for(int i = 0;i < sz;i++){ A1[i] = A[i].x;A2[i] = A[i].x;A3[i] = A[i].x; B1[i] = B[i].x;B2[i] = B[i].x;B3[i] = B[i].x; } auto C1 = ntt1.convolution(A1,B1); auto C2 = ntt2.convolution(A2,B2); auto C3 = ntt3.convolution(A3,B3); int rs = C1.size(); std::vector<mint> res(rs); for(int i = 0;i < rs;i++){ std::vector<long long> r = {C1[i].x,C2[i].x,C3[i].x},m = {2013265921,998244353,469762049}; res[i] = garner(r,m,MOD); } return res; } std::vector<long long> convolution(const std::vector<long long>& A,const std::vector<long long>& B){ assert(A.size() == B.size()); int sz = A.size(); std::vector<long long> A1(sz),B1(sz),A2(sz),B2(sz),A3(sz),B3(sz); for(int i = 0;i < sz;i++){ A1[i] = A[i] % 2013265921;B1[i] = B[i] % 2013265921; A2[i] = A[i] % 998244353;B2[i] = B[i] % 998244353; A3[i] = A[i] % 469762049;B3[i] = B[i] % 469762049; } auto C1 = ntt1.convolution(A1,B1); auto C2 = ntt2.convolution(A2,B2); auto C3 = ntt3.convolution(A3,B3); int rs = C1.size(); std::vector<long long> res(rs); for(int i = 0;i < rs;i++){ std::vector<long long> r = {C1[i],C2[i],C3[i]},m = {2013265921,998244353,469762049}; res[i] = garner(r,m,MOD) % MOD; } return res; } }; int main(){ myset(); NTT_all<mod1> ntt; using mint = NTT_all<mod1>::mint; int N; cin >> N; vector<mint> A(N + 1),B(N + 1); rep(i,N + 1)cin >> A[i]; rep(i,N + 1)cin >> B[i]; // reverse(all(A));reverse(all(B)); auto C = ntt.convolution(A,B); mint ans = 0; rep(i,N + 1)ans += C[i]; cout << ans << "\n"; debug(A,B); debug(C); }