QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471644#9106. Zayin and DirichletbambamRE 0ms0kbC++172.3kb2024-07-11 00:19:432024-07-11 00:19:43

Judging History

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

  • [2024-07-11 00:19:43]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-11 00:19:43]
  • 提交

answer

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1005, maxk=105, maxc=1e5+5;
const int lim=1e5;
const LL mo=998244353;

int n,k,m,k2;
LL a[maxn];

LL Pow(LL x,LL y) {
	LL re=1;
	for(; y; y>>=1, x=x*x%mo) if (y&1) re=re*x%mo;
	return re;
}

LL C[maxc+maxk][maxk];
LL C_Pre(int n,int k) {
	fo(i,0,n) {
		C[i][0]=1;
		fo(j,1,(i>k ?k :i)) {
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			C[i][j]=(C[i][j]>=mo) ?C[i][j]%mo :C[i][j];
		}
	}
}

int id[maxn][maxn],tot;
LL f[2*maxn][maxn],c[maxn],invcm;
void dp(int i) {
	fo(ki,0,k)
		fo(index,0,n) f[id[i][ki]][index]=0;
	
	if (i==0 && c[i]<0) {
		fo(ki,0,k)
			fo(index,0,n)
				for(int x=0, neg=1; x<=ki && x<=-c[i]; x++, neg*=-1)
					(f[id[i][ki]][index]+=f[id[i+1][ki-x]][index]*C[-c[i]][x]*neg%mo+mo)%=mo;
	} else if (c[i]==0) {
		fo(ki,0,k)
			fo(index,0,n) f[id[i][ki]][index]=f[id[i+1][ki]][index];
	} else {
		fo(ki,0,k)
			fo(index,0,n)
				for(int x=0; x<=ki && x*i<=index; x++)
					(f[id[i][ki]][index]+=f[id[i+1][ki-x]][index-x*i]*C[c[i]-1+x][x])%=mo;
	}
}
LL dp_res() {
	dp(m);
	
	fd(i,m-1,0) {
		int now=m*(k-1)+i;
		LL res=(a[now]-f[id[i+1][k]][now]+mo)%mo;
		c[i]=res*invcm%mo;
		if (i>0 && c[i]>lim) return lim+500;
			else if (i==0 && c[i]>lim && c[i]-mo<-lim) return lim+500;
				else if (i==0 && c[i]>lim) c[i]-=mo;
		dp(i);
	}
	
	fo(i,0,n) if (a[i]!=f[id[0][k]][i]) return lim+500;
	
	LL re=0;
	fo(i,0,m) (re+=abs(c[i]))%=mo;
	return re;
}

void Output() {
	printf("%d\n",k2*m);
	fo(i,0,k2*m) printf("%lld ",(f[id[0][k2]][i]%mo+mo)%mo);
	puts("");
	exit(0);
}

int main() {
	scanf("%d %d %d",&n,&k,&k2);
	fo(i,0,n) scanf("%lld",&a[i]);
	
	if (n%k!=0) {puts("-1"); return 0;}
	m=n/k;
	
	C_Pre(lim+k,k);
	
	fo(i,0,m)
		fo(j,0,k) id[i][j]=++tot;
	id[m+1][0]=++tot;
	
	if (n==0 && a[0]==0) {puts("0\n0"); return 0;}
	f[tot][0]=1;
	for(c[m]=1; c[m]<=lim; c[m]++) if (C[c[m]-1+k][k]==a[n]) {
		invcm=Pow(C[c[m]-1+k-1][k-1],mo-2);
		if (dp_res()<=lim) Output();
	}
	if (m==0) {
		int neg=(k&1) ?-1 :1 ;
		for(c[0]=-1; c[0]>=-lim; c[0]--)
			if ((C[-c[0]][k]*neg+mo)%mo==a[0]) {
				dp_res();
				Output();
			}
	}
	
	puts("-1");
}

详细

Test #1:

score: 0
Runtime Error

input:

2 2 1
1 1 1

output:


result: