并不对劲的复健训练-bzoj5339:loj2578:p4593:[TJOI2018]教科书般的亵渎

题目大意

题解

先将\(a\)排序。

\(k\)看上去等于怪的血量连续段的个数，但是要注意当存在\(a_i+1=a_{i+1}\)时，虽然它们之间的连续段为空，但是还要算上；而当\(a_m=n\)时，最后一段连续段不用算。

考虑进行游戏的过程：设当前最大血量为\(p\)，正在打出第\(q\)张亵渎，那么得到的分数是：\(\sum\limits_{i=1}^p i^k-\sum\limits_{i=q}^{m}(a_i-a_{q-1})^k\)。

后一部分可以直接求。

前一部分\(\sum\limits_{i=1}^p i^k\)，通过观察查看题解发现求它的公式是个关于\(p\)的\(k+1\)次多项式，可以把\(p=1,2,...,k+2\)的值代入暴力求解，得到\(k+2\)个在该多项式的曲线上的点，然后通过拉格朗日插值求该多项式。

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

#define LL long long

#define maxn 57

using namespace std;

LL read()

{

    LL x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    int f=0;char ch[20];

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

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

    return;

}

const LL mod=1e9+7;

LL n,a[maxn];

int t,m,f[maxn],b[maxn],qy[maxn],ans,sz,k;

int mul(int x,int y){int res=1;while(y){if(y&1)res=(LL)res*x%mod;x=(LL)x*x%mod,y>>=1;}return res;}

int mo(int x){return x>=mod?x-mod:x;}

void prew()

{

	rep(i,1,sz)qy[i]=mo(qy[i-1]+mul(i,k)),f[i]=0;

	f[0]=1;

	rep(i,1,sz)dwn(j,i,1)f[j]=mo(f[j]+(LL)f[j-1]*(mod-i)%mod);

	reverse(f,f+sz+1);

	rep(i,1,sz)

	{

		int lst=0,num=1,nyx=mul(mod-i,mod-2);

		rep(j,1,sz)if(i!=j)num=(LL)num*mo(i-j+mod)%mod;

		num=(LL)mul(num,mod-2)*qy[i]%mod;

		rep(i,0,sz-1)

		{

			lst=(LL)mo(f[i]-lst+mod)*nyx%mod,b[i]=mo(b[i]+(LL)lst*num%mod);

		}

	}

}

int getf(LL x)

{

	if(x<=0)return 0;

	x%=mod;

	int res=0,now=1;

	rep(i,0,sz-1)res=mo(res+(LL)b[i]*now%mod),now=(LL)now*x%mod;

	return res;

}

int main()

{

    t=read();

    while(t--)

    {

		n=read(),m=read(),ans=0;k=m+1;

	    rep(i,1,m)a[i]=read();

	    sort(a+1,a+m+1);

	    if(a[m]==n)k--;

	    else a[++m]=n+1;sz=k+2;

		prew();

	    rep(i,1,m)

	    {

	    	ans=mo(ans+getf(a[m]-a[i-1]-1));

	    	rep(j,i,m-1)ans=mo(ans-mul(a[j]-a[i-1],k)+mod);

	    }

		write(ans);

		rep(i,0,sz)b[i]=0;

	}

	return 0;

}

一些感想

说到求自然数幂和，就不得不说某年省选day1t3……

仔细想想，对于某些手很健康的人来说，可能写拉格朗日插值比写暴力的正解快？

巴特西

并不对劲的复健训练-bzoj5339:loj2578:p4593:[TJOI2018]教科书般的亵渎

题目大意

题解

代码

一些感想

最新文章

热门文章