题解 P5223 【Function】

· · 题解

提供一种乱搞做法

由递推式可以知道,f[i][j](j\leq i)一定是一个关于i的j-1次函数。具体证明可以通过数学归纳法，这里略去。所以可以考虑打表打出f[2000][1000]以内的值，用拉格朗日重心插值法O(k)插值并求值，总复杂度O(k^2)。

#include <stdio.h>
#include <string.h>
typedef long long ll;
const int N=2002,M=1002,p=998244353;
int f[N][M],w[M],l[M],r[M],ifac[M],inv[M];
ll qq;
int main()
{
    register int n,m,i,j,k,tq,q,ans=0;
    scanf("%lld%d",&qq,&m);
    n=m<<1;tq=qq%p;tq+=p;
    for (i=1;i<=n;i++) f[i][1]=1;
    for (i=2;i<=n;i++)
    {
        k=i;if (k>m) k=m;
        for (j=1;j<=k;j++)
        {
            if ((f[i][j]=f[i-1][j]+f[i][j-1])>=p) f[i][j]-=p;
            if ((f[i][j]=f[i][j]+f[i-1][j-1])>=p) f[i][j]-=p;
        }
    }
    ifac[0]=ifac[1]=inv[1]=1;
    for (i=2;i<=m;i++) ifac[i]=(ll)ifac[i-1]*(inv[i]=p-(ll)p/i*inv[p%i]%p)%p;
    for (i=1;i<=m;i++)
    {
        k=(i<<1)-1;q=tq-i;
        for (j=i;j<=k;j++) w[j-i]=f[j][i];k-=i;
        for (j=0;j<=k;j++)
        {
            w[j]=(ll)w[j]*ifac[j]%p*ifac[k-j]%p;
            if ((j^k)&1) w[j]=p-w[j];
        }
        l[0]=q;
        for (j=1;j<=k;j++) l[j]=(ll)l[j-1]*(q-j)%p;
        r[k]=q-k;
        for (j=k-1;~j;j--) r[j]=(ll)r[j+1]*(q-j)%p;
        ans=(ans+(ll)r[1]*w[0]+(ll)l[k-1]*w[k])%p;
        for (j=1;j<k;j++) ans=(ans+(ll)l[j-1]*r[j+1]%p*w[j])%p;
    }
    printf("%d",(ans+1)%p);
}