結果

問題 No.931 Multiplicative Convolution
ユーザー beetbeet
提出日時 2019-11-22 22:21:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 215 ms / 2,000 ms
コード長 5,267 bytes
コンパイル時間 3,138 ms
コンパイル使用メモリ 220,480 KB
最終ジャッジ日時 2025-01-08 05:12:50
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 4 ms
5,248 KB
testcase_07 AC 21 ms
6,400 KB
testcase_08 AC 205 ms
30,724 KB
testcase_09 AC 184 ms
30,528 KB
testcase_10 AC 207 ms
30,416 KB
testcase_11 AC 184 ms
30,208 KB
testcase_12 AC 165 ms
28,312 KB
testcase_13 AC 204 ms
30,400 KB
testcase_14 AC 215 ms
30,852 KB
testcase_15 AC 215 ms
30,944 KB
testcase_16 AC 203 ms
30,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
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> rev(P);
{
Int res=1;
for(Int i=0;i<P;i++){
rev[res]=i;
res=res*rt%P;
}
}
vector<Int> A(P),B(P);
for(Int i=1;i<P;i++){
A[rev[i]]=as[i];
B[rev[i]]=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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0