---

正题

题目链接:https://www.luogu.com.cn/problem/P4593

---

题目大意

场上有若干只怪，最高的为$n$，每个怪血量不同，有$m$个血量不存在。

不停释放亵渎（全场打一，如果有怪死亡就再次生效），每次一个怪被攻击会产生价值$x^k$（$x$是该怪亵渎前的血量，$k$是打完总共需要释放的亵渎数量）。

求价值和

---

解题思路

直接扭了输出价值和为0

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

然后先不考虑空位答案产生的影响，第一次亵渎产生的代价为${\sum }_{i=1}^n{i}^k$

然后考虑空位位置开始亵渎，如果开始位置为$q$，那么代价为${\sum }_{i=1}^{n-q}{i}^k$

然后减去产生的影响，对于第一次亵渎需要减去的是$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$次函数，我们可以先求出$1\sim 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);} }

总结

以上是生活随笔为你收集整理的P4593-[TJOI2018]教科书般的亵渎【拉格朗日差值】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。