[Luogu 4593] [TJOI2018]教科书般的亵渎

Posted on | Edited on | In , | Views:

题目链接

Luogu 4593

做法

有个显然的结论，干掉这些怪需要亵渎的数量为$m+1$张，那么第一次亵渎的分数为

而第二次到第$m+1$亵渎的分数也都是形如这个形式。
后面一项求和的项数很少，我们可以直接暴力，而前面一项则是经典的自然数幂和问题，我们使用拉格朗日插值求解。
对于$\sum\limits_{i=1}^{n}i^k$，我们把它看成一个关于n的函数，通过伯努利数或斯特林数或其他各种各样的做法我们知道他是一个$k+1$次函数，所以我们只要先暴力代入$i=[0,k+1]$计算答案，再暴力插值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
const int P=1000000007;
int ans,m,T; 
int x[N],y[N],w[N];
LL a[N];
LL n;
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
inline int Inc(int a,int b){
    return (a+b>=P)?(a+b-P):(a+b);
}
inline int ksm(int a,int b){
    int ret=1;
    for (;b;b>>=1,a=1ll*a*a%P) if (b&1) ret=1ll*ret*a%P;
    return ret;
}
inline int inv(int a){
    return ksm(a,P-2);
}
void init(){
    y[0]=0;
    x[0]=0;
    for (int i=1;i<=m+1;i++){
        x[i]=i;
        y[i]=Inc(y[i-1],ksm(i,m));
        //printf("%d %d\n",x[i],y[i]);
    }
    for (int i=0;i<=m+1;i++){
        w[i]=1;
        for (int j=0;j<=m+1;j++){
            if (i!=j) w[i]=1ll*w[i]*(x[i]-x[j]+P)%P;
        }
        w[i]=inv(w[i]);
    }
}
int query(LL t){
    int l=1;
    t%=P; 
    for (int i=0;i<=m+1;i++) if (t==x[i]) return y[i];
    for (int i=0;i<=m+1;i++) l=1ll*l*(t-x[i]+P)%P;
    int ans=0;
    for (int i=0;i<=m+1;i++){
        ans=Inc(ans,1ll*y[i]*l%P*inv(Inc(t-x[i],P))%P*w[i]%P);
    }
    //printf("query %lld %d\n",t,ans);
    return ans;
}
int main(){
    read(T);
    while (T--){
        read(n),read(m);
        for (int i=1;i<=m;i++){
            read(a[i]);
        }
        sort(a+1,a+m+1);
        m++;
        init();
        ans=0;
        for (int i=1;i<=m;i++){
            ans=Inc(ans,query(n-a[i-1]));
            for (int j=i;j<m;j++){
                ans=Inc(ans-ksm((a[j]-a[i-1])%P,m),P);
            }
        }
        printf("%d\n",ans);
    } 
    return 0;
}