网站空间使用方法,小微企业名录查询官网,大型网站开发的书,响水做网站哪家好正题
题目链接:https://www.luogu.com.cn/problem/P4593 题目大意
场上有若干只怪#xff0c;最高的为nnn#xff0c;每个怪血量不同#xff0c;有mmm个血量不存在。
不停释放亵渎#xff08;全场打一#xff0c;如果有怪死亡就再次生效#xff09;#xff0c;每次一… 正题
题目链接:https://www.luogu.com.cn/problem/P4593 题目大意
场上有若干只怪最高的为nnn每个怪血量不同有mmm个血量不存在。
不停释放亵渎全场打一如果有怪死亡就再次生效每次一个怪被攻击会产生价值xkx^kxkxxx是该怪亵渎前的血量kkk是打完总共需要释放的亵渎数量。
求价值和 解题思路
直接扭了输出价值和为0
首先可以知道km1km1km1
然后先不考虑空位答案产生的影响第一次亵渎产生的代价为∑i1nik\sum_{i1}^ni^k∑i1nik
然后考虑空位位置开始亵渎如果开始位置为qqq那么代价为∑i1n−qik\sum_{i1}^{n-q}i^k∑i1n−qik
然后减去产生的影响对于第一次亵渎需要减去的是aika_i^kaik
然后对面后面减去的是∑i1n∑ji1naiaj−ai\sum_{i1}^n\sum_{ji1}^na_{i}^{a_j-a_i}∑i1n∑ji1naiaj−ai
考虑如何计算∑i1xik\sum_{i1}^xi^k∑i1xik我们可以知道这个是一个x1x1x1项的kkk次函数我们可以先求出1∼x21\sim x21∼x2的点用拉格朗日差值计算答案即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N60,XJQ1e97;
ll n,m,k,T,ans;
ll f[N],fac[N],a[N];
ll power(ll x,ll b){ll ans1;x%XJQ;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
ll slove(ll x){if(xk2)return f[x];ll ans0;for(ll i1;ik2;i){ll yf[i];for(ll j1;jk2;j){if(ij)continue;(y*(x-jXJQ)%XJQ*power(i-jXJQ,XJQ-2)%XJQ)%XJQ;}(ansy)%XJQ;}return ans;
}
int main()
{fac[0]1;for(ll i1;iN;i)fac[i]fac[i-1]*i%XJQ;scanf(%lld,T);while(T--){scanf(%lld%lld,n,m);for(ll i1;im;i)scanf(%lld,a[i]);km1;sort(a1,a1m);while(a[m]n)n--,m--,k--;for(ll i1;ik2;i)f[i](f[i-1]power(i,k))%XJQ;ansslove(n);for(ll i1;im;i)(ansslove(n-a[i]))%XJQ;for(ll i1;im;i)(ansXJQ-power(a[i],k))%XJQ;for(ll i1;im;i)for(ll ji1;jm;j)(ansXJQ-power(a[j]-a[i],k))%XJQ;printf(%lld\n,ans);}
}
