---

正題

題目鏈接:https://www.luogu.com.cn/problem/P4593

---

題目大意

場上有若干只怪，最高的為$n$，每個怪血量不同，有$m$個血量不存在。

不停釋放褻瀆（全場打一，如果有怪死亡就再次生效），每次一個怪被攻擊會產(chǎn)生價值$x^k$（$x$是該怪褻瀆前的血量，$k$是打完總共需要釋放的褻瀆數(shù)量）。

求價值和

---

解題思路

直接扭了輸出價值和為0

首先可以知道$k=m+1$

然后先不考慮空位答案產(chǎn)生的影響，第一次褻瀆產(chǎn)生的代價為${\sum }_{i=1}^n{i}^k$

然后考慮空位位置開始褻瀆，如果開始位置為$q$，那么代價為${\sum }_{i=1}^{n?q}{i}^k$

然后減去產(chǎn)生的影響，對于第一次褻瀆需要減去的是$a_i^k$

然后對面后面減去的是${\sum }_{i=1}^n{\sum }_{j=i+1}^n{a}_i^{a_j?a_i}$

考慮如何計算${\sum }_{i=1}^x{i}^k$，我們可以知道這個是一個$x+1$項的$k$次函數(shù)，我們可以先求出$1～x+2$的點，用拉格朗日差值計算答案即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=60,XJQ=1e9+7; ll n,m,k,T,ans; ll f[N],fac[N],a[N]; ll power(ll x,ll b){ll ans=1;x%=XJQ;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } ll slove(ll x){if(x<=k+2)return f[x];ll ans=0;for(ll i=1;i<=k+2;i++){ll y=f[i];for(ll j=1;j<=k+2;j++){if(i==j)continue;(y*=(x-j+XJQ)%XJQ*power(i-j+XJQ,XJQ-2)%XJQ)%=XJQ;}(ans+=y)%=XJQ;}return ans; } int main() {fac[0]=1;for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%XJQ;scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++)scanf("%lld",&a[i]);k=m+1;sort(a+1,a+1+m);while(a[m]==n)n--,m--,k--;for(ll i=1;i<=k+2;i++)f[i]=(f[i-1]+power(i,k))%XJQ;ans=slove(n);for(ll i=1;i<=m;i++)(ans+=slove(n-a[i]))%=XJQ;for(ll i=1;i<=m;i++)(ans+=XJQ-power(a[i],k))%=XJQ;for(ll i=1;i<=m;i++)for(ll j=i+1;j<=m;j++)(ans+=XJQ-power(a[j]-a[i],k))%=XJQ;printf("%lld\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的P4593-[TJOI2018]教科书般的亵渎【拉格朗日差值】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。