QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471645 | #9106. Zayin and Dirichlet | bambam | RE | 0ms | 0kb | C++17 | 2.6kb | 2024-07-11 00:21:02 | 2024-07-11 00:21:03 |
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,1,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");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
2 2 1 1 1 1