QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#471645#9106. Zayin and DirichletbambamRE 0ms0kbC++172.6kb2024-07-11 00:21:022024-07-11 00:21:03

Judging History

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

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

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

output:


result: