結果
| 問題 | No.931 Multiplicative Convolution |
| コンテスト | |
| ユーザー |
 beet
|
| 提出日時 | 2019-11-22 22:19:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,851 bytes |
| 記録 | |
| コンパイル時間 | 2,726 ms |
| コンパイル使用メモリ | 226,720 KB |
| 最終ジャッジ日時 | 2025-01-08 05:11:29 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 TLE * 9 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
struct FastIO{
FastIO(){
cin.tie(0);
ios::sync_with_stdio(0);
}
}fastio_beet;
template<typename T>
T mod_pow(T a,long long n,T mod){
using ll = long long;
T res(1);
while(n){
if(n&1) res=(ll)res*a%mod;
a=(ll)a*a%mod;
n>>=1;
}
return res;
}
template<typename T>
map<T, Int> factorize(T x){
map<T, Int> res;
for(Int i=2;i*i<=x;i++){
while(x%i==0){
x/=i;
res[i]++;
}
}
if(x!=1) res[x]++;
return res;
}
template<typename T>
T order(T x,T MOD){
static map<T, vector<T>> dp;
vector<T> &ps=dp[MOD];
if(ps.empty()){
auto fs=factorize(MOD-1);
for(auto p:fs) ps.emplace_back(p.first);
}
T res=MOD-1;
for(T p:ps){
while(res%p==0){
if(mod_pow(x,res/p,MOD)!=1) break;
res/=p;
}
}
return res;
}
// find x s.t. a^x = b (x >= 0)
template<typename T>
T mod_log(T a,T b,T mod){
using ll = long long;
ll g=1;
{
ll m=mod;
while(m){
g=(ll)g*a%mod;
m>>=1;
}
}
g=__gcd(g,(ll)mod);
ll c=0,t=1;
while(t%g){
if(t==b) return c;
t=t*a%mod;
c++;
}
// not found
if(b%g) return mod;
t/=g;b/=g;
const ll n=mod/g;
ll h=0,gs=1;
while(h*h<n){
gs=gs*a%n;
++h;
}
unordered_map<ll, ll> bs;
{
ll s=0,e=b;
while(s<h){
e=e*a%n;
bs[e]=++s;
}
}
{
ll s=0,e=t;
while(s<n){
e=e*gs%n;
s+=h;
if(bs.count(e))
return c+s-bs[e];
}
}
// not found
return mod;
}
template<typename T,T MOD = 1000000007>
struct Mint{
static constexpr T mod = MOD;
T v;
Mint():v(0){}
Mint(signed v):v(v){}
Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}
Mint pow(long long k){
Mint res(1),tmp(v);
while(k){
if(k&1) res*=tmp;
tmp*=tmp;
k>>=1;
}
return res;
}
static Mint add_identity(){return Mint(0);}
static Mint mul_identity(){return Mint(1);}
Mint inv(){return pow(MOD-2);}
Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
Mint& operator/=(Mint a){return (*this)*=a.inv();}
Mint operator+(Mint a) const{return Mint(v)+=a;}
Mint operator-(Mint a) const{return Mint(v)-=a;}
Mint operator*(Mint a) const{return Mint(v)*=a;}
Mint operator/(Mint a) const{return Mint(v)/=a;}
Mint operator-() const{return v?Mint(MOD-v):Mint(v);}
bool operator==(const Mint a)const{return v==a.v;}
bool operator!=(const Mint a)const{return v!=a.v;}
bool operator <(const Mint a)const{return v <a.v;}
static Mint comb(long long n,Int k){
Mint num(1),dom(1);
for(Int i=0;i<k;i++){
num*=Mint(n-i);
dom*=Mint(i+1);
}
return num/dom;
}
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}
constexpr Int bmds(Int x){
const Int v[] = {1012924417, 924844033, 998244353,
897581057, 645922817};
return v[x];
}
constexpr Int brts(Int x){
const Int v[] = {5, 5, 3, 3, 3};
return v[x];
}
template<Int X>
struct NTT{
static constexpr Int md = bmds(X);
static constexpr Int rt = brts(X);
using M = Mint<Int, md>;
vector< vector<M> > 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;
M w=M(rt).pow((md-1)/(i<<1));
M rw=w.inv();
rts[i].resize(i);rrts[i].resize(i);
rts[i][0]=M(1);rrts[i][0]=M(1);
for(Int k=1;k<i;k++){
rts[i][k]=rts[i][k-1]*w;
rrts[i][k]=rrts[i][k-1]*rw;
}
}
}
void ntt(vector<M> &as,bool f,Int n=-1){
if(n==-1) n=as.size();
assert((n&(n-1))==0);
ensure_base(n);
for(Int i=0,j=1;j+1<n;j++){
for(Int k=n>>1;k>(i^=k);k>>=1);
if(i>j) swap(as[i],as[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++){
M z=as[i+j+k]*(f?rrts[i][k]:rts[i][k]);
as[i+j+k]=as[j+k]-z;
as[j+k]+=z;
}
}
}
if(f){
M tmp=M(n).inv();
for(Int i=0;i<n;i++) as[i]*=tmp;
}
}
vector<M> multiply(vector<M> as,vector<M> bs){
Int need=as.size()+bs.size()-1;
Int sz=1;
while(sz<need) sz<<=1;
as.resize(sz,M(0));
bs.resize(sz,M(0));
ntt(as,0);ntt(bs,0);
for(Int i=0;i<sz;i++) as[i]*=bs[i];
ntt(as,1);
as.resize(need);
return as;
}
vector<Int> multiply(vector<Int> as,vector<Int> bs){
vector<M> am(as.size()),bm(bs.size());
for(Int i=0;i<(Int)am.size();i++) am[i]=M(as[i]);
for(Int i=0;i<(Int)bm.size();i++) bm[i]=M(bs[i]);
vector<M> cm=multiply(am,bm);
vector<Int> cs(cm.size());
for(Int i=0;i<(Int)cs.size();i++) cs[i]=cm[i].v;
return cs;
}
};
template<Int X> constexpr Int NTT<X>::md;
template<Int X> constexpr Int NTT<X>::rt;
//INSERT ABOVE HERE
signed main(){
Int P;
cin>>P;
vector<Int> as(P),bs(P);
for(Int i=1;i<P;i++) cin>>as[i];
for(Int i=1;i<P;i++) cin>>bs[i];
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<Int> ud(1,P-1);
Int rt=ud(mt);
while(order(rt,P)!=P-1) rt=ud(mt);
vector<Int> A(P),B(P);
for(Int i=1;i<P;i++){
A[mod_log(rt,i,P)]=as[i];
B[mod_log(rt,i,P)]=bs[i];
}
NTT<2> ntt;
using M = decltype(ntt)::M;
auto C=ntt.multiply(A,B);
vector<M> cs(P);
for(Int i=0;i<(Int)C.size();i++)
cs[mod_pow(rt,i,P)]+=C[i];
for(Int i=1;i<P;i++){
if(i>1) cout<<" ";
cout<<cs[i];
}
cout<<endl;
return 0;
}