QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#14490 | #1425. Div | jahova | WA | 11ms | 52792kb | C++20 | 2.0kb | 2021-10-07 11:01:52 | 2022-05-17 00:34:18 |
Judging History
answer
#include <bits/stdc++.h>
#define N 2000006
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
const ll mod=998244353;
int now_limit;
int rev[N];
ll wq[20][N],fac[N],inv[N];
ll ksm(ll x,ll y){
ll res=1; while(y){ if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; }
return res;
}
void init_NTT(int limit){
if(limit==now_limit) return;
now_limit=limit; int l=0; while((1<<l)<limit)l++;
for(int i=0;i<limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
if(wq[0][0]==0){
while(limit<1000000) limit<<=1;
for(int mid=1,l=0;mid<limit;mid<<=1,l++){
wq[l][0]=1,wq[l][1]=ksm(3,(mod-1)/(mid<<1));
for(int k=2;k<mid;k++) wq[l][k]=wq[l][k-1]*wq[l][1]%mod;
}
}
}
void NTT(vec &a,int limit,int flag){
init_NTT(limit);
while(a.size()<limit) a.push_back(0);
for(int i=0;i<limit;i++) if(i<rev[i])swap(a[i],a[rev[i]]);
ll x,y;
for(int mid=1,l=0;mid<limit;mid<<=1,l++)
for(int j=0;j<limit;j+=(mid<<1))
for(int k=0;k<mid;k++){
x=a[j+k],y=a[j+k+mid]*wq[l][k]%mod;
a[j+k]=(x+y)%mod,a[j+k+mid]=(x-y+mod)%mod;
}
if(flag==-1){
x=ksm(limit,mod-2);
for(int i=0;i<limit;i++) a[i]=a[i]*x%mod;
reverse(&a[1],&a[limit]);
}
}
vec g,f;
int n,k,inv2;
void cdq_NTT(int l,int r){
if(r-l<2){
if(l>k)
for(int i=(l-k+1)/2;i+i<l;i++) f[l]=(f[l]+f[i]*f[l-i]%mod)%mod;
int m=min((l+k)/2,l);
for(int i=(l+1)/2;i<=m;i++) f[l]=(f[l]+f[i]*f[l-i]%mod)%mod;
f[l]=f[l]*inv2%mod;
return;
}
int mid=(l+r+1)>>1;
cdq_NTT(l,mid);
vec a,b; a=vector<ll>(&f[l],&f[mid]); b=vector<ll>(&f[0],&f[min(r-l,mid)]);
int limit=1; while(limit<r-l) limit<<=1;
NTT(a,limit,1),NTT(b,limit,1);
for(int i=0;i<limit;i++) a[i]=a[i]*b[i]%mod;
NTT(a,limit,-1);
if(l!=0) for(int i=mid;i<r;i++) f[i]=(f[i]+a[i-l]+a[i-l])%mod;
else for(int i=mid;i<r;i++) f[i]=(f[i]+a[i-l])%mod;
cdq_NTT(mid,r);
}
int main(){
// freopen("test.in","r",stdin);
cin>>n>>k;
f.resize(n+1);
f[1]=2; inv2=ksm(2,mod-2);
cdq_NTT(0,n+1);
cout<<f[n]<<'\n';
}
详细
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 52792kb
input:
3 5 2 1 0 1 0 1 0 1 0 1 0 5 3 -1 2 -1 1 -1 0 1 1 -1 1 12 3 -1 0 -1 7 1 8 1 8 -1 4 -1 6 1 8 1 2 1 5 1 2 -1 9 1 5
output:
499122178
result:
wrong answer 1st numbers differ - expected: '1', found: '499122178'