[BZOJ5339] [TJOI2018]教科书般的亵渎

题目链接

Solution

随便推一推，可以发现瓶颈在求\(\sum_{i=1}^n i^k\)，关于这个可以看看拉格朗日插值法。

复杂度\(O(Tm^2)\)。

#include<bits/stdc++.h>

using namespace std;

#define int long long 

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

const int maxn = 100;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 1e9+7;

int qpow(int a,int x) {

	int res=1;a%=mod;

	for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;

	return res;

}

int m,a[maxn],pw[maxn],pre[maxn],suf[maxn],fac[maxn],ifac[maxn];

int calc(int n,int k) {

	k++;suf[k+1]=fac[0]=ifac[0]=1;pre[0]=n%mod;

	for(int i=1;i<=k;i++) pre[i]=pre[i-1]*((n-i)%mod)%mod;

	for(	for(int i=1;i<=k;i++) pre[i]=pre[i-1]*((n-i)%mod)%mod;

	for(int i=k;~i;i--) suf[i]=suf[i+1]*((n-i)%mod)%mod;

	int i=k;~i;i--) suf[i]=suf[i+1]*((n-i)%mod)%mod;

	for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;

	ifac[k]=qpow(fac[k],mod-2);

	for(int i=k-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;

	int ans=0;

	for(int i=1;i<=k;i++) ans=(ans+(((k-i)&1)?-1:1)*pw[i]*pre[i-1]%mod*suf[i+1]%mod*ifac[i]%mod*ifac[k-i]%mod);

	return ans;

}

void solve() {

	int N,n;read(N),read(m);for(int i=1;i<=m;i++) read(a[i]);n=N;

	for(int i=1;i<=m+3;i++) pw[i]=(qpow(i,m+1)+pw[i-1])%mod;

	int ans=0;sort(a+1,a+m+1);

	for(int i=0;i<=m;i++) {

		ans+=calc(n-a[i],m+1);

		for(int j=i;j<=m;j++) ans=(ans-qpow(a[j]-a[i],m+1))%mod;

	}write((ans+mod)%mod);

}

signed main() {

	int t;read(t);

	while(t--) solve();

	return 0;

}

巴特西

[BZOJ5339] [TJOI2018]教科书般的亵渎

题目链接

Solution

最新文章

热门文章