結果
問題 | No.931 Multiplicative Convolution |
ユーザー | fumofumofuni |
提出日時 | 2022-10-16 19:02:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 247 ms / 2,000 ms |
コード長 | 5,405 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 214,920 KB |
実行使用メモリ | 22,452 KB |
最終ジャッジ日時 | 2024-06-27 13:30:48 |
合計ジャッジ時間 | 6,546 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 27 ms
5,416 KB |
testcase_08 | AC | 247 ms
22,452 KB |
testcase_09 | AC | 183 ms
21,984 KB |
testcase_10 | AC | 227 ms
22,036 KB |
testcase_11 | AC | 183 ms
21,892 KB |
testcase_12 | AC | 183 ms
20,716 KB |
testcase_13 | AC | 233 ms
22,044 KB |
testcase_14 | AC | 241 ms
22,324 KB |
testcase_15 | AC | 239 ms
22,296 KB |
testcase_16 | AC | 234 ms
22,136 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 vtpl(x,y,z) vector<tuple<x,y,z>> #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[9]={0,1,-1,0,1,1,-1,-1,0}; const ll dx[9]={1,0,0,-1,1,-1,1,-1,0}; 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 { //MOD9のNTT auto c=NTT::mul(a,b)で受け取り。 std::vector<ll> tmp; size_t sz = 1; inline ll powMod(ll n, ll p, ll m) { ll res = 1; while (p) { if (p & 1) res = res * n % m; n = n * n % m; p >>= 1; } return res; } inline ll invMod(ll n, ll m) { return powMod(n, m - 2, m); } ll extGcd(ll a, ll b, ll &p, ll &q) { if (b == 0) { p = 1; q = 0; return a; } ll d = extGcd(b, a%b, q, p); q -= a/b * p; return d; } pair<ll, ll> ChineseRem(const vector<ll> &b, const vector<ll> &m) { ll r = 0, M = 1; for (int i = 0; i < (int)b.size(); ++i) { ll p, q; ll d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d) if ((b[i] - r) % d != 0) return make_pair(0, -1); ll tmp = (b[i] - r) / d * p % (m[i]/d); r += M * tmp; M *= m[i]/d; } return make_pair((r+M+M)%M, M); } template <ll Mod, ll PrimitiveRoot> struct NTTPart { static std::vector<ll> ntt(std::vector<ll> 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; ll e = powMod(PrimitiveRoot, (Mod - 1) / sz * i, Mod); if (inv) e = invMod(e, Mod); ll 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] + w * cur[(((j << 1) + i) & mask) + k]) % Mod; } w = w * e % Mod; } ++p; } if (p & 1) std::swap(a, tmp); if (inv) { ll invSz = invMod(sz, Mod); for (size_t i = 0; i < sz; ++i) a[i] = a[i] * invSz % Mod; } return a; } static std::vector<ll> mul(std::vector<ll> a, std::vector<ll> b) { a = ntt(a); b = ntt(b); for (size_t i = 0; i < sz; ++i) a[i] = a[i] * b[i] % Mod; a = ntt(a, true); return a; } }; std::vector<ll> mul(std::vector<ll> a, std::vector<ll> b) { 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); vector<ll> c=NTTPart<998244353,3>::mul(a, b); c.resize(m); return c; } std::vector<ll> mul_ll(std::vector<ll> a, std::vector<ll> b) { 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); vector<ll> c=NTTPart<998244353,3>::mul(a, b); vector<ll> d=NTTPart<1224736769,3>::mul(a, b); c.resize(m);d.resize(m); vector<ll> e(m); rep(i,m)e[i]=ChineseRem({c[i],d[i]},{998244353,1224736769}).first; return e; } }; ll pow_mod(ll a,ll n, ll mod) { a%=mod;if(a==0)return 0; ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } constexpr int primitive_root_constexpr(int m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 469762049) return 3; if (m == 754974721) return 11; if (m == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; (long long)(i)*i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) { x /= i; } } } if (x > 1) { divs[cnt++] = x; } for (int g = 2;; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (pow_mod(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) return g; } } int main(){ //ll p=200003; ll p;cin >> p; ll r=primitive_root_constexpr(p); vl a(p);rep(i,p-1)cin >> a[i+1]; vl b(p);rep(i,p-1)cin >> b[i+1]; vl trans(p); vl inverse(p); ll cnt=1; rep(i,p-1){ trans[cnt]=i; inverse[i]=cnt; cnt=cnt*r%p; } vector<ll> dp(p),ep(p); rep(i,p)dp[trans[i]]+=a[i]; rep(i,p)ep[trans[i]]+=b[i]; dp=NTT::mul_ll(dp,ep); vl ans(p); rep(i,p*2-1){ //if(dp[i])cout << inverse[i%(p-1)] <<" " << dp[i] << endl; ans[inverse[i%(p-1)]]+=dp[i]; } rep(i,p-1)cout << ans[i+1]%MOD9 <<" ";cout << endl; //cout << ans%MOD9 << endl; }