「TJOI 2018」教科书般的亵渎

「TJOI 2018」教科书般的亵渎

解题思路 :

考虑将没有出现的血量集合 \(m_i\) 从小到大排序，观察发现对于每一个 \(m_i\) ，其会使得所有血量 \(-m_i\)

设此时场上的最大血量为 \(c\) ，那么其能产生的贡献就是 \((\sum_{j=1}^{c} j^k) - \sum_{j=i}^{m} m_i\ ^k\)

由于 \(m\) 很小，计算后面式子的复杂度可以忽略不计，问题就转化为快速计算前面的式子

观察发现前面的式子其实就是一个 \(k + 1\) 次的多项式，暴力插值求解即可

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

	int f = 0, ch = 0; x = 0;

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

	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

	if(f) x = -x;

}

#define int ll

const int Mod = 1000000007;

vector<int> x, y;

int a[105], n, m;

inline int Pow(int a, int b){

	int ans = 1; a %= Mod;

	for(; b; b >>= 1, a = a * a % Mod)

		if(b & 1) ans = ans * a % Mod;

	return ans;

}

inline void Prework(int k){

	x.clear(), y.clear();

	for(int i = 1, now = 0; i <= k + 2; i++)

		x.push_back(i), y.push_back((now += Pow(i, k)) %= Mod);

}

inline int calc(int now){

	int res = 0;

	for(int i = 0; i < x.size(); i++){

		int tmp = y[i];

		for(int j = 0; j < x.size(); j++) if(j != i)

			(tmp *= (now - x[j]) % Mod * Pow(x[i] - x[j], Mod - 2) % Mod) %= Mod;

		(res += tmp) %= Mod;

	}

	return res;

}

inline void solve(){

	int ans = 0, now = 0;

	read(n), read(m), Prework(m + 1);

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

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

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

		(ans += calc(n - now)) %= Mod;

		for(int j = i; j <= m; j++) (ans -= Pow(a[j] - now, m + 1)) %= Mod;

		now = a[i];

	}

	(ans += calc(n - now)) %= Mod;

	cout << ((ans % Mod) + Mod) % Mod << endl;

}

signed main(){

	int T; read(T); while(T--) solve();

	return 0;

}