多项式做法卡常求助
查看原帖
多项式做法卡常求助
365021
masterhuang楼主2022/6/6 22:15

我已近尽力了,最终还是卡不过去,有大佬帮忙看看嘛,就是n,m都-1后求1(1xx2)(1x)n\frac{1}{(1-x-x^2)(1-x)^n}的第mm项,用了常系数齐次线性递推这题Potassium题解的前半段的思想求解,希望大佬帮忙看看吧

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const LL mod=998244353,_g=332748118;//逆元
const int g=3,N=8e5+5;
LL fan[N],n,m;
inline LL rd()
{
    LL x=0,zf=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') (ch=='-')and(zf=-1),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*zf;
}
inline void wr(LL x)
{
    if(x==0) return putchar('0'),putchar(' '),void();
    short num[35],len=0;
    while(x) num[++len]=x%10,x/=10;
    for(int i=len;i>=1;i--) putchar(num[i]+'0');
    putchar(' ');
}
inline LL ksm(LL x,LL p)
{
    LL s=1;
    for(;p;(p&1)&&(s=s*x%mod),x=x*x%mod,p>>=1);
    return s;
}
inline void ntt(vector<LL>&c,LL zf,LL mmax)
{
	c.resize(mmax+1);
    for(LL i=0;i<mmax;i++) if(i<fan[i]) swap(c[i],c[fan[i]]);
    for(LL k=(mmax>>1);k>=1;k>>=1)
    {
        LL nu=mmax/k/2,mul=ksm(zf==1?g:_g,(mod-1)/(nu<<1));
        for(LL l=0;l<k;l++)
            for(LL i=0,j=1;i<nu;i++,j=j*mul%mod){LL xx=c[l*nu*2+i],yy=j*c[l*nu*2+i+nu]%mod;c[l*nu*2+i]=(xx+yy)%mod,c[l*nu*2+i+nu]=(xx-yy+mod)%mod;}
    }
    if(zf==1) return;
    LL inv=ksm(mmax,mod-2);
    for(LL i=0;i<mmax;i++) c[i]=c[i]*inv%mod;
}
struct node
{
	vector<LL>F;
	inline LL ci(){return F.size()-1;}//返回幂次 
}a,b;
inline void init(LL nn,LL &mmax)
{
	mmax=1;for(;mmax<=nn;mmax<<=1);
	for(LL i=0;i<mmax;i++) fan[i]=(fan[i>>1]>>1)|((i&1)?(mmax>>1):0);
}
inline void mul(node f,node g,node &h)
{
	LL len=f.ci()+g.ci(),mmax;
	init(len,mmax);h.F.resize(mmax+1);
	ntt(f.F,1,mmax);ntt(g.F,1,mmax);
	for(LL i=0;i<=mmax;i++) h.F[i]=f.F[i]*g.F[i]%mod;
	ntt(h.F,-1,mmax);h.F.resize(len+1);
}
inline LL dfs(LL p,node a,node b)
{
	for(;p;p>>=1)
	{
		LL i;
		node c=b;c.F.resize(b.ci()+1);
		for(i=1;i<=b.ci();i+=2) c.F[i]=mod-c.F[i];
		mul(a,c,a);mul(b,c,b);
		for(i=p&1;i<=a.ci();i+=2) a.F[i/2]=a.F[i];
		a.F.resize(i/2);
		for(i=0;i<=b.ci();i+=2) b.F[i/2]=b.F[i];
		b.F.resize(i/2);
	}
	return a.F[0]*ksm(b.F[0],mod-2)%mod;
}
signed main()
{
	n=rd();m=rd();n--;m--;
	b.F.resize(n+3);
	for(LL i=0,j=1;i<=n;i++)
	{
	    LL zf=((n-i)&1)?-1:1;
	    b.F[n-i]=(zf*j+mod)%mod;j=j*(n-i)%mod*ksm(i+1,mod-2)%mod;
	}
	node c=b;
	for(LL i=0;i<=n;i++)
	{
	    b.F[i+1]=(b.F[i+1]-c.F[i]+mod)%mod;
	    b.F[i+2]=(b.F[i+2]-c.F[i]+mod)%mod;
	}
	a.F.resize(1);a.F[0]=1;
	printf("%lld\n",dfs(m,a,b));
	return 0;
}
2022/6/6 22:15
加载中...