結果
問題 | No.754 畳み込みの和 |
ユーザー | fumofumofuni |
提出日時 | 2021-02-03 02:11:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 5,000 ms |
コード長 | 4,648 bytes |
コンパイル時間 | 2,477 ms |
コンパイル使用メモリ | 215,968 KB |
実行使用メモリ | 12,392 KB |
最終ジャッジ日時 | 2024-06-30 00:06:20 |
合計ジャッジ時間 | 4,070 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 199 ms
12,392 KB |
testcase_01 | AC | 201 ms
12,392 KB |
testcase_02 | AC | 201 ms
12,260 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<n;i++) #define repl(i,l,r) for(ll i=(l);i<(r);i++) #define per(i,n) for(ll i=(n)-1;i>=0;i--) #define perl(i,r,l) for(ll i=r-1;i>=l;i--) #define fi first #define se second #define pb push_back #define ins insert #define pqueue(x) priority_queue<x,vector<x>,greater<x>> #define all(x) (x).begin(),(x).end() #define CST(x) cout<<fixed<<setprecision(x) #define rev(x) reverse(x); using ll=long long; using vl=vector<ll>; using vvl=vector<vector<ll>>; using pl=pair<ll,ll>; using vpl=vector<pl>; using vvpl=vector<vpl>; const ll MOD=1000000007; const ll MOD9=998244353; const int inf=1e9+10; const ll INF=4e18; //const ll dy[8]={-1,0,1,0,1,1,-1,-1}; //const ll dx[8]={0,-1,0,1,1,-1,1,-1}; template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } namespace NTT { // int32型のmodが取れるFFT。auto c=NTT::mul(a,b,mod)で受け取り。TIME指定。 // ChineseRemと組み合わせてlong longにもできる std::vector<int> tmp; size_t sz = 1; inline int powMod(int n, int p, int m) { int res = 1; while (p) { if (p & 1) res = (ll)res * n % m; n = (ll)n * n % m; p >>= 1; } return (int)res; } inline int invMod(int n, int m) { return powMod(n, m - 2, m); } template <int Mod, int PrimitiveRoot> struct NTTPart { static std::vector<int> ntt(std::vector<int> a, bool inv = false) { size_t mask = sz - 1; size_t p = 0; for (size_t i = sz >> 1; i >= 1; i >>= 1) { auto& cur = (p & 1) ? tmp : a; auto& nex = (p & 1) ? a : tmp; int e = powMod(PrimitiveRoot, (Mod - 1) / sz * i, Mod); if (inv) e = invMod(e, Mod); int w = 1; for (size_t j = 0; j < sz; j += i) { for (size_t k = 0; k < i; ++k) { nex[j + k] = (cur[((j << 1) & mask) + k] + (ll)w * cur[(((j << 1) + i) & mask) + k]) % Mod; } w = (ll)w * e % Mod; } ++p; } if (p & 1) std::swap(a, tmp); if (inv) { int invSz = invMod(sz, Mod); for (size_t i = 0; i < sz; ++i) a[i] = (ll)a[i] * invSz % Mod; } return a; } static std::vector<int> mul(std::vector<int> a, std::vector<int> b) { a = ntt(a); b = ntt(b); for (size_t i = 0; i < sz; ++i) a[i] = (ll)a[i] * b[i] % Mod; a = ntt(a, true); return a; } }; constexpr int M[] = {1224736769, 469762049, 167772161}; constexpr int PR[] = {3, 3, 3}; constexpr int NTT_CONVOLUTION_TIME = 3; /* X := max(a)*max(b)*max(|a|, |b|) のとき, NTT_CONVOLUTION_TIME <- 1: X < 1224736769 = 1.2*10^ 9 ~ 2^30 NTT_CONVOLUTION_TIME <- 2: X < 575334854091079681 = 5.8*10^17 ~ 2^59 NTT_CONVOLUTION_TIME <- 3: X < 2^86 (32bit * 32bit * 10^7くらいまで) */ inline void garner(std::vector<int> *c, int mod) { if (NTT_CONVOLUTION_TIME == 1) { for(auto& x : c[0]) x %= mod; } else if (NTT_CONVOLUTION_TIME == 2) { const int r01 = invMod(M[0], M[1]); for (size_t i = 0; i < sz; ++i) { c[1][i] = (c[1][i] - c[0][i]) * (ll)r01 % M[1]; if (c[1][i] < 0) c[1][i] += M[1]; c[0][i] = (c[0][i] + (ll)c[1][i] * M[0]) % mod; } } else if (NTT_CONVOLUTION_TIME == 3) { const int R01 = invMod(M[0], M[1]); const int R02 = invMod(M[0], M[2]); const int R12 = invMod(M[1], M[2]); const int M01 = (ll)M[0] * M[1] % mod; for (size_t i = 0; i < sz; ++i) { c[1][i] = (c[1][i] - c[0][i]) * (ll)R01 % M[1]; if (c[1][i] < 0) c[1][i] += M[1]; c[2][i] = ((c[2][i] - c[0][i]) * (ll)R02 % M[2] - c[1][i]) * R12 % M[2]; if (c[2][i] < 0) c[2][i] += M[2]; c[0][i] = (c[0][i] + (ll)c[1][i] * M[0] + (ll)c[2][i] * M01) % mod; } } } std::vector<int> mul(std::vector<int> a, std::vector<int> b, int mod) { for (auto& x : a) x %= mod; for (auto& x : b) x %= mod; size_t m = a.size() + b.size() - 1; sz = 1; while (m > sz) sz <<= 1; tmp.resize(sz); a.resize(sz, 0); b.resize(sz, 0); std::vector<int> c[NTT_CONVOLUTION_TIME]; if (NTT_CONVOLUTION_TIME >= 1) c[0] = NTTPart<M[0], PR[0]>::mul(a, b); if (NTT_CONVOLUTION_TIME >= 2) c[1] = NTTPart<M[1], PR[1]>::mul(a, b); if (NTT_CONVOLUTION_TIME >= 3) c[2] = NTTPart<M[2], PR[2]>::mul(a, b); for (auto& v : c) v.resize(m); garner(c, mod); return c[0]; } }; // !!! CHECK NTT_CONVOLUTION_TIME !!! int main(){ ll n;cin >> n;n++; vector<int> a(n),b(n); rep(i,n)cin >> a[i]; rep(i,n)cin >> b[i]; auto c=NTT::mul(a,b,MOD); ll ans=0; rep(i,n)ans=(ans+c[i])%MOD; cout << ans <<endl; }