QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#589961 | #621. 多项式指数函数 | leingy5an | 0 | 2206ms | 86796kb | C++17 | 3.2kb | 2024-09-25 20:50:46 | 2024-09-25 20:50:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int mod=998244353;
ll qpow(ll x,ll y=mod-2,ll ans=1){
for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
namespace Poly{
const int N=1<<21,g=3;
int lim,rev[N],pw[N];
void Init(){
int x=qpow(g,(mod-1)/N);
pw[N/2]=1;
for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
for(int i=N/2-1;i>=1;i--)pw[i]=pw[i<<1];
}
namespace Public{
using poly=vector<int>;
void init(int n){
for(lim=1;lim<n;lim<<=1);
for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
}
void NTT(int *a,int op){
static ull f[N];
for(int i=0;i<lim;i++)f[i]=a[rev[i]];
for(int len=1;len<lim;len<<=1){
for(int i=0;i<lim;i+=len<<1){
for(int j=0;j<len;j++){
int x=f[i|j|len]*pw[len|j]%mod;
f[i|j|len]=f[i|j]+mod-x,f[i|j]+=x;
}
}
if(__lg(len)%16==0){
for(int i=0;i<lim;i++)f[i]%=mod;
}
}
for(int i=0;i<lim;i++)a[i]=f[i]%mod;
if(op<0){
reverse(a+1,a+lim);
int x=qpow(lim);
for(int i=0;i<lim;i++)a[i]=1ll*a[i]*x%mod;
}
}
poly operator * (const poly &a,const poly &b){
int n=a.size(),m=b.size(),k=n+m-1;
static int A[N],B[N];
init(k);
copy(all(a),A),fill(A+n,A+lim,0);
copy(all(b),B),fill(B+m,B+lim,0);
NTT(A,1),NTT(B,1);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,-1);
return poly{A,A+k};
}
poly& operator %= (poly &a,const int &k){
if(a.size()>k)a.resize(k);
return a;
}
poly operator % (const poly &a,const int &k){
poly b(a);
return b%=k;
}
poly operator + (const poly &a,const poly &b){
poly c(max(a.size(),b.size()),0);
for(int i=0;i<a.size();i++)c[i]=a[i];
for(int i=0;i<b.size();i++)(c[i]+=b[i])%=mod;
return c;
}
poly operator - (const poly &a,const poly &b){
poly c(max(a.size(),b.size()),0);
for(int i=0;i<a.size();i++)c[i]=a[i];
for(int i=0;i<b.size();i++)(c[i]+=mod-b[i])%=mod;
return c;
}
//H(x)=H0(x)-G(H(x))/G'(H(x))
poly inv(const poly &a,int n=-1){
if(n==-1)n=a.size();
if(n==1)return poly(1,qpow(a[0]));
int m=(n+1)/2;
auto b=inv(a%m,m);
return b*(poly{2}-a*b%n)%n;
}
poly qiudao(const poly &a){
poly b(a.size()-1);
for(int i=1;i<a.size();i++)b[i-1]=1ll*i*a[i]%mod;
return b;
}
poly jifen(const poly &a){
poly b(a.size()+1,0);
b[1]=1;
for(int i=2;i<b.size();i++)b[i]=1ll*b[mod%i]*(mod-mod/i)%mod;
for(int i=1;i<b.size();i++)b[i]=1ll*b[i]*a[i-1]%mod;
return b;
}
poly ln(const poly &a,int n=-1){
if(n==-1)n=a.size();
return jifen(qiudao(a)%n*inv(a,n)%n)%n;
}
poly exp(const poly &a,int n=-1){
if(n==-1)n=a.size();
if(n==1)return poly{1};
int m=(n+1)/2;
auto b=exp(a%m,m);
return b*(poly{1}+a-ln(b,n))%n;
}
}
}
using namespace Poly::Public;
int n;
int main(){
// Poly::Init();
scanf("%d",&n);
poly a(n);
for(int &x:a)scanf("%d",&x);
a=exp(a);
for(int x:a)printf("%d ",x);
puts("");
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9964kb
input:
100 0 158447743 737554986 671332600 489297184 754299210 115728600 816221630 819073359 691660913 910093246 562505672 355119917 385019894 611338034 123976316 122342952 82142434 796101450 994778874 575255638 493217967 652609142 662045597 783871340 470398790 241710709 754059035 534582325 836438174 95789...
output:
58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 58003456 580...
result:
wrong answer 1st numbers differ - expected: '1', found: '58003456'
Test #2:
score: 0
Wrong Answer
time: 3ms
memory: 10456kb
input:
5000 0 354399910 26360255 630255958 717224815 366941345 333979504 905420494 38176634 475666562 611197455 433060682 509600868 845217181 520468365 529689763 431747498 192834976 685184103 287994809 273221518 522219732 427553800 10872482 525061651 448069946 183539744 610476003 840167561 241104955 404100...
output:
401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 401067842 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '401067842'
Test #3:
score: 0
Wrong Answer
time: 37ms
memory: 10964kb
input:
30000 0 147199510 293972908 780683378 633744119 800282266 162025013 919460711 939176222 298044997 277962122 729446209 455723129 756791462 84697115 579989768 945113433 549318980 229266945 869577376 103161009 960973464 440149102 836285074 687333626 638404974 184096947 370164754 454531549 142629528 150...
output:
83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 83713348 837...
result:
wrong answer 1st numbers differ - expected: '1', found: '83713348'
Test #4:
score: 0
Wrong Answer
time: 181ms
memory: 16884kb
input:
100000 0 279349013 196667718 617497154 78288698 996674429 180463729 304956112 173800460 352061138 224505321 119706982 726737325 564797383 757014824 888433954 747100108 723246918 645172013 184990722 321964667 456686646 138153830 701558524 317746193 650472945 49496183 864461799 982372868 582778782 242...
output:
659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 659489691 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '659489691'
Test #5:
score: 0
Wrong Answer
time: 2206ms
memory: 86796kb
input:
1000000 0 204517192 162156394 729093416 352181074 335898409 357987855 386581690 26622360 437289663 34104646 938411413 659876244 293619518 291093969 909364118 179765868 89417259 632261731 375051702 493701794 771716785 682264158 329653513 86558030 9195128 957504298 22555222 384175297 128022431 5957444...
output:
803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 803302682 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '803302682'