QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#14490#1425. DivjahovaWA 11ms52792kbC++202.0kb2021-10-07 11:01:522022-05-17 00:34:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-17 00:34:18]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:52792kb
  • [2021-10-07 11:01:52]
  • 提交

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'