P5488 差分与前缀和 NTT Lucas定理多项式

LINK：差分与前缀和

这道题和loj的一个人的高三楼相似。

也略有不同先考虑前缀和:设G(x)为原式的普通型生成函数 \(F(x)=1+x+x^2+...\)

那么其实求的是 \(G(x)*(F(x))^k\)的前n项。k很大不能直接做多项式快速幂想直接展开系数似乎也做不到。

利用Lucas定理 \(F(x)^k\equiv F(x)^{sp+r}\equiv F(x)^{sp}*F(x)^r (mod p)\)

后面的东西再次展开\((F(x)^p)^s*F(x)^r\) 忘了一件事情为了方便设\(F(x)=1+x\)

那么显见\(((1+x)^p)^s*F(x)^r=(1+x^p)^s*F(x)^r\)

由于最后求出前n项所以上式等价于\(F(x)^r\)

其实这里取的\(F(x)\)有点特殊了实际上\(F(x)=\frac{1}{1-x}\)也是一样的。

对于差分也同理所以可以使k直接对mod取模。

其实根据上式还可以反向证明Lucas定理这里不再赘述。

考虑如何求出系数可以使用多项式快速幂也可以选择EXP那一套当然最直观的是第i项系数为\(C(i+k-1,k-1)\)可以直接线性递推得到。

差分同理至此问题得到解决。

code

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-8

#define sq sqrt

#define S second

#define F first

#define mod 1004535809

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=((ll)x*10+ch-'0')%mod;ch=getc();}

    return x*f;

}

const int MAXN=300010,G=3;

int n,k,T,lim;

int a[MAXN],rev[MAXN];

int b[MAXN],O[MAXN],in[MAXN];

inline int ksm(int b,int p)

{

	int cnt=1;

	while(p)

	{

		if(p&1)cnt=(ll)cnt*b%mod;

		b=(ll)b*b%mod;p=p>>1;

	}

	return cnt;

}

inline void NTT(int *a,int op)

{

	vep(0,lim,i)if(i<rev[i])swap(a[i],a[rev[i]]);

	for(int len=2;len<=lim;len=len<<1)

	{

		int mid=len>>1;

		int wn=ksm(G,op==1?(mod-1)/len:mod-1-(mod-1)/len);

		vep(1,mid,i)O[i]=(ll)O[i-1]*wn%mod;

		for(int j=0;j<lim;j+=len)

		{

			vep(0,mid,i)

			{

				int x=a[i+j],y=(ll)a[i+j+mid]*O[i]%mod;

				a[i+j]=(x+y)%mod;a[i+j+mid]=(x-y+mod)%mod;

			}

		}

	}

	if(op==-1)

	{

		int INV=ksm(lim,mod-2);

		vep(0,lim,i)a[i]=(ll)a[i]*INV%mod;

	}

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(k);get(T);O[0]=1;

	vep(0,n,i)get(a[i]);

	if(T==0)

	{

		in[1]=b[0]=1;b[1]=k;

 		vep(2,n,i)

		{

			in[i]=(ll)in[mod%i]*(mod-mod/i)%mod;

			b[i]=(ll)b[i-1]*in[i]%mod*(i+k-1)%mod;

		}

	}

	else

	{

		in[1]=b[0]=1;b[1]=mod-k;

		rep(2,min(k,n-1),i)

		{

			in[i]=(ll)in[mod%i]*(mod-mod/i)%mod;

			b[i]=mod-(ll)b[i-1]*in[i]%mod*(k-i+1)%mod;

		}

	}

	lim=1;while(lim<n+n)lim=lim<<1;

	vep(0,lim,i)rev[i]=rev[i>>1]>>1|((i&1)?lim>>1:0);

	NTT(a,1);NTT(b,1);

	vep(0,lim,i)a[i]=(ll)a[i]*b[i]%mod;

	NTT(a,-1);

	vep(0,n,i)printf("%d ",a[i]);

	return 0;

}

巴特西

P5488 差分与前缀和 NTT Lucas定理多项式

最新文章

热门文章

巴特西

P5488 差分与前缀和 NTT Lucas定理 多项式

最新文章

热门文章

P5488 差分与前缀和 NTT Lucas定理多项式