luogu P4948 数列求和推式子简单数学推导二项式拉格朗日插值

LINK:数列求和

每次遇到这种题目都不太会写。但是做法很简单.

终有一天我会成功的。

考虑类似等比数列求和的东西帽子戏法一下.

设\(f(k)=\sum_{i=1}^ni^ka^i\)

考虑\(af(k)\)这个式子两式做差.

\((a-1)f(k)=n^n\cdot a^{n+1}-a+\sum_{i=2}^n{a^i((i-1)^k-i^k)}\)

右边直接二项式展开然后交换求和顺序可得.

\((a-1)f(k)=n^k\cdot a^{n+1}-a+\sum_{j=0}^{k-1}C(k,j)(-1)^{k-j}(f_j-a)\)

然后除以a-1就可以\(k^2\)推了.

注意a==1时也可以类似这样推式子不过直接拉格朗日插值就最简单的做法。

code

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

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cctype>

#include<queue>

#include<deque>

#include<stack>

#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 10000000000000000ll

#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 rep(p,n,i) for(RE ll i=p;i<=n;++i)

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

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

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

#define pii pair<ll,ll>

#define mk make_pair

#define RE register

#define P 1000000007ll

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

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

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-10

#define sq sqrt

#define S second

#define F first

#define mod 1000000007

using namespace std;

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

inline char gc()

{

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

}

inline ll read()

{

	RE ll x=0,f=1;RE char ch=gc();

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

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}

	return x*f;

}

const ll MAXN=2010;

ll n,k,a;

ll f[MAXN],fac[MAXN],inv[MAXN];

inline ll ksm(ll b,ll p)

{

	ll cnt=1;

	while(p)

	{

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

		b=b*b%mod;p=p>>1;

	}

	return cnt;

}

inline ll C(ll a,ll b){return a<b?0:fac[a]*inv[b]%mod*inv[a-b]%mod;}

inline ll lag(ll x,ll n)

{

	ll ans=0;x%=mod;

	rep(1,n,i)

	{

		ll sum=1,ww=1;

		f[i]=(f[i-1]+ksm(i,k))%mod;

		rep(1,n,j)

		{

			if(i==j)continue;

			sum=sum*(x-j)%mod;

			ww=ww*(i-j)%mod;

		}

		sum=sum*ksm(ww,mod-2)%mod;

		ans=(ans+f[i]*sum)%mod;

	}

	return (ans+mod)%mod;

}

inline void solve_1()

{

	putl(lag(n,k+2));

}

inline void solve_2()

{

	fac[0]=1;

	rep(1,k,i)fac[i]=fac[i-1]*i%mod;

	inv[k]=ksm(fac[k],mod-2);

	fep(k-1,0,i)inv[i]=inv[i+1]*(i+1)%mod;

	ll IN=ksm(a-1,mod-2),cc;

	f[0]=((cc=ksm(a,(n+1)%(mod-1)))-a)*IN%mod;

	n%=mod;

	rep(1,k,i)

	{

		cc=cc*n%mod;ll ans=cc-a;

		rep(0,i-1,j)ans=(ans+C(i,j)*((i-j)&1?-1:1)*(f[j]-a))%mod;

		f[i]=ans*IN%mod;

	}

	putl((f[k]+mod)%mod);

}

signed main()

{

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

	get(n);get(a);get(k);

	if(a==1)solve_1();

	else solve_2();

	return 0;

}

巴特西

luogu P4948 数列求和推式子简单数学推导二项式拉格朗日插值

最新文章

热门文章

巴特西

luogu P4948 数列求和 推式子 简单数学推导 二项式 拉格朗日插值

最新文章

热门文章

luogu P4948 数列求和推式子简单数学推导二项式拉格朗日插值