結果
| 問題 |
No.931 Multiplicative Convolution
|
| コンテスト | |
| ユーザー |
 Cinnamoroll
|
| 提出日時 | 2020-08-10 02:01:59 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 672 ms / 2,000 ms |
| コード長 | 11,493 bytes |
| コンパイル時間 | 2,094 ms |
| コンパイル使用メモリ | 187,248 KB |
| 実行使用メモリ | 28,048 KB |
| 最終ジャッジ日時 | 2024-10-06 00:51:19 |
| 合計ジャッジ時間 | 5,657 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 |
ソースコード
// warm heart, wagging tail,and a smile just for you!
// ███████████
// ███╬╬╬╬╬╬╬╬╬╬███
// ███╬╬╬╬╬████╬╬╬╬╬╬███
// ███████████ ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
// █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
// ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
// ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
// ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
// █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
// ██████████████ ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
// ███████ █████ ███████████████████
//
#include "bits/stdc++.h"
using namespace std;
#define INF (1<<30)
#define LINF (1LL<<60)
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR2(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define RFOR2(i,a,b) for(int i = (b);i>=(a);--i)
#define REP(i,n) FOR(i,0,(n))
#define REP2(i,n) FOR2(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define RREP2(i,n) RFOR2(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl
#define SP << " " <<
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b) {a=b; return true;} else return false;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b) {a=b; return true;} else return false;}
#define MSB(x) (63-__builtin_clzll(x))
#define pcnt(x) (__builtin_popcountll(x))
#define parity(i,j) (i&(1LL<<j))
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
vector<int> MODS = { 1000000007, 998244353 }; // 実行時に決まる
template<int IND = 0> struct Fp {
long long val;
int MOD = MODS[IND];
constexpr Fp(long long v = 0) noexcept : val(v % MODS[IND]) {
if (val < 0) val += MOD;
}
constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
friend constexpr ostream& operator << (ostream &os, const Fp<IND>& x) noexcept {
return os << x.val;
}
friend constexpr istream& operator >> (istream &is, Fp<IND>& x) noexcept {
return is >> x.val;
}
friend constexpr Fp<IND> modpow(const Fp<IND> &a, long long n) noexcept {
if (n == 0) return 1;
auto t = modpow(a, n / 2);
t = t * t;
if (n & 1) t = t * a;
return t;
}
};
using mint = Fp<1>; // MODを変える場合は値を変更
typedef vector<mint> vec;
typedef vector<vector<mint>> mat;
vec fact,inv;
void init(int n){
fact.assign(n+1,1);
inv.assign(n+1,1);
REP(i,n) fact[i+1] = fact[i]*(i+1), inv[i+1] /= fact[i+1];
}
mint cmb(int n, int r){
if(n < r) return 0;
return fact[n]*inv[r]*inv[n-r];
}
int get_root(int p) {
// pの原子根を求める
for(int i=2;i<p;i++) {
set<int> S;
int x=1,j;
while(1) {
if(S.size()==p-1) return i;
if(S.count(x)) break;
S.insert(x);
x=x*i%p;
}
}
assert(0);
}
constexpr int bmds(int x){
if(x==0) return 1012924417;
if(x==1) return 924844033;
if(x==2) return 998244353;
if(x==3) return 897581057;
if(x==4) return 645922817;
}
constexpr int brts(int x){
if(x==0) return 5;
if(x==1) return 5;
if(x==2) return 3;
if(x==3) return 3;
if(x==4) return 3;
}
template<int X>
struct NTT{
static constexpr int md = bmds(X);
static constexpr int rt = brts(X);
inline int add(int a,int b){
a+=b;
if(a>=md) a-=md;
return a;
}
inline int mul(int a,int b){
return 1LL*a*b%md;
}
inline int pow(int a,int b){
int res=1;
while(b){
if(b&1) res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
inline int inv(int x){
return pow(x,md-2);
}
vector<vector<int> > rts,rrts;
void ensure_base(int n){
if((int)rts.size()>=n) return;
rts.resize(n);rrts.resize(n);
for(int i=1;i<n;i<<=1){
if(!rts[i].empty()) continue;
int w=pow(rt,(md-1)/(i<<1));
int rw=inv(w);
rts[i].resize(i);rrts[i].resize(i);
rts[i][0]=1;rrts[i][0]=1;
for(int k=1;k<i;k++){
rts[i][k]=mul(rts[i][k-1],w);
rrts[i][k]=mul(rrts[i][k-1],rw);
}
}
}
void ntt(vector<int> &a,bool f,int n=-1){
if(n==-1) n=a.size();
assert((n&(n-1))==0);
for(int i=0,j=1;j+1<n;j++){
for(int k=n>>1;k>(i^=k);k>>=1);
if(i>j) swap(a[i],a[j]);
}
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=i*2){
for(int k=0;k<i;k++){
int z=mul(a[i+j+k],f?rrts[i][k]:rts[i][k]);
a[i+j+k]=add(a[j+k],md-z);
a[j+k]=add(a[j+k],z);
}
}
}
if(f){
int tmp=inv(n);
for(int i=0;i<n;i++) a[i]=mul(a[i],tmp);
}
}
vector<int> multiply(vector<int> &a,vector<int> &b){
int need=a.size()+b.size()-1;
int sz=1;
while(sz<need) sz<<=1;
ensure_base(sz);
vector<int> f(sz),g(sz);
for(int i=0;i<(int)a.size();i++) f[i]=a[i];
for(int i=0;i<(int)b.size();i++) g[i]=b[i];
ntt(f,0);ntt(g,0);
for(int i=0;i<sz;i++) f[i]=mul(f[i],g[i]);
ntt(f,1);
f.resize(need);
return f;
}
};
void solve(){
int P;
cin >> P;
vector<int> a(P);
REP(i,P-1) cin >> a[i+1];
vector<int> b(P);
REP(i,P-1) cin >> b[i+1];
if(P==2){
cout << (mint)a[1]*b[1] << endl;
return;
}
int g = get_root(P);
vector<int> x(P-1,0),y(P-1,0); // x[i] = a[g^i]
int v = 1;
REP(i,P-1){
x[i] = a[v];
y[i] = b[v];
v *= g; v %= P;
}
NTT<2> ntt;
auto z = ntt.multiply(x,y); // c[g^i] = sum(j+k==i){a[g^j]*b[g^k]} -> z[i] = sum(j+k==i){x[j]*y[k]}
vec ans(P);
v = 1;
REP(i,z.size()){
ans[v] += z[i];
v *= g; v %= P;
}
REP(i,P-1) cout << ans[i+1] << " ";
cout << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while(T--) solve();
return 0;
}