多项式

拉格朗日插值

朴素做法

$n+1$ 个点可以确定一个 $n$ 次多项式。拉格朗日插值可以实现，对于某个 $n$ 次多项式函数 $f(x)$ ，如果我们已知了这 $n+1$ 个点，就可以 $O(n^2)$ 的时间复杂度求出 $f(k)$

具体来说，我们我们知道了多项式函数上的 $n+1$ 个点 $(x_i,y_i)$，然后有公式：

$$f(k)=\sum_{i=1}^{n+1} y_i \prod_{j\neq i} \frac{k-x_j}{x_i-x_j}$$

点为连续情况

如果 $x_i$ 是连续的，比如 $x_1=1,x_2=2,...,x_i=i$，那么我们可以通过预处理，$O(n)$ 的时间复杂度求出 $f(k)$

首先预处理出阶乘 $fac_i$ 以及阶乘逆元，然后对于要求出的点 $k$，预处理出下面两值：

$$pre_i=\prod_{j=1}^i k-j$$

$$suf_i=\prod_{j=i}^{n+1}k-j$$

然后有公式：

$$f(k)=\sum_{i=1}^{n+1}y_i\frac{pre_{i-1}\times suf_{i+1}}{fac_{i-1}\times fac_{n+1-i}\times (-1)^{n+1-i}}$$

题目

F. The Sum of the k-th Powers

https://codeforces.com/problemset/problem/622/F

题目描述

求 $(\sum_{i=1}^ni^k)\pmod{10^9+7}$

数据范围

$1\le n \le 10^9$，$0\le k \le 10^6$

笔记

$k$ 次方求和，求和公式是 $k+1$ 次的，我们先暴力算出 $k+2$ 个点，然后插值即可

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> pii;
#define _ 2000006
int fac[_],inv[_],pre[_],suf[_],y[_];
inline int qpow(int a,int p,int res=1){for(;p;p>>=1,a=a*a%mod)if(p&1)res=res*a%mod;return res;}
inline void subtask(){
    fac[0]=1;
    for(int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i%mod;
    int n,k;cin>>n>>k;
    for(int i=1;i<=k+2;i++) y[i]=(y[i-1]+qpow(i,k))%mod;
    pre[0]=1;
    for(int i=1;i<=k+2;i++) pre[i]=pre[i-1]*(n-i)%mod;
    suf[k+3]=1;
    for(int i=k+2;i>=1;i--) suf[i]=suf[i+1]*(n-i)%mod;
    int ans=0;
    for(int i=1;i<=k+2;i++) ans+=((k+2-i)%2==0?1:-1)*y[i]*pre[i-1]%mod*suf[i+1]%mod*qpow(fac[i-1],mod-2)%mod*qpow(fac[k+2-i],mod-2)%mod,ans%=mod;
    cout<<(ans+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

P4593 [TJOI2018] 教科书般的亵渎

https://www.luogu.com.cn/problem/P4593

题目描述

现在有 $1\sim n$，共 $n$ 个数字，然后去掉其中 $m$ 个数字。然后每次操作，都可以让所有的数字减一，如果减完之后有数字变为 $0$，则去掉该数字，然后再把所有的数字减一，由数字归零引发的减一也算在这次操作中。我们设 $k$ 为需要多少次操作才能把所有的数字归零。每次操作，对于每个数字，都会产生 $x^k$ 的分数，其中 $x$ 为减一之前的数字。

求出把所有数字归零后，获得的总分数。多组测试数据

数据范围

• 对于 $10\%$ 的数据，有 $m=0$；
• 对于 $20\%$ 的数据，有 $m\leq1$；
• 对于 $30\%$ 的数据，有 $m\leq2$
• 对于 $40\%$ 的数据，有 $m\leq3$；
• 对于 $50\%$ 的数据，有 $m\leq4$；
• 对于 $60\%$ 的数据，有 $m\leq5$；
• 对于 $100\%$ 的数据，有 $m\leq50$，$n\leq10^{13}$，$1 \le a_i <n$。

笔记

首先需要看出 $k=m+1$，手推几个样例然后感性理解一下就能得出来了

去掉数字后，会把 $1\sim n$ 分成若干数字连续的段

然后我们把贡献拆开，对于一个数字，考虑他会对总分数产生什么样的贡献。设被去掉的数字为 $a_i$，然后设 令 $a_0=0$，我们发现数字 $x$ 对答案的贡献为 $\sum_{i=0}^m(x-a_i)^k$，其中只计算小于 $x$ 的 $a_i$。手推几个样例然后感性理解一下就能得出来了

我们又发现，如果 $a_i$ 固定，$x$ 在某个区间上连续变化的话，$x-a_i$ 也是连续变化的，$(x-a_i)^k$ 就可以像上道题那样求出

于是答案变为了 $\sum_{i=0}^m\sum_{x=l_j}^{r_j} (x-a_i)^k$

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> pii;
int fac[66],inv[66],y[66],n,m,pre[66],suf[66];
inline int qpow(int a,int p,int res=1){for(;p;p>>=1,a=a*a%mod)if(p&1)res=res*a%mod;return res;}
inline void subtask(){
    cin>>n>>m;
    vector<int> ve;
    for(int i=1,x;i<=m;i++) cin>>x,ve.push_back(x);
    ve.push_back(0);sort(ve.begin(),ve.end());
    int end=n;
    for(int i=ve.size()-1;i>=0;i--) if(ve[i]==end) m--,end--,n--;
    int k=m+1;
    for(int i=1;i<=k+2;i++) y[i]=(y[i-1]+qpow(i,k))%mod;
    auto f=[k](int x){
        if(x==0) return (long long)0;
        pre[0]=1;
        for(int i=1;i<=k+2;i++) pre[i]=pre[i-1]*(x-i)%mod;
        suf[k+3]=1;
        for(int i=k+2;i>=1;i--) suf[i]=suf[i+1]*(x-i)%mod;
        int res=0;
        for(int i=1;i<=k+2;i++) res+=((k+2-i)%2==0?1:-1)*y[i]*pre[i-1]%mod*suf[i+1]%mod*inv[i-1]%mod*inv[k+2-i]%mod,res%=mod;
        return (res+mod)%mod;
    };
    auto flr=[f](int l,int r){return (f(r)-f(l-1)+mod)%mod;};

    vector<pii> ran;
    int l=1;
    for(auto x:ve){
        if(!x) continue;
        if(x==l) l++;
        else{
            ran.push_back(pii(l,x-1));
            l=x+1;
        }
    }
    if(l<=n) ran.push_back(pii(l,n));
    int res=0;
    for(auto to:ran){
        for(auto x:ve){
            if(x>to.first) break;
            res+=flr(to.first-x,to.second-x);res%=mod;
        }
    }
    cout<<res<<endl;
}
signed main(){
    fac[0]=1;
    for(int i=1;i<=60;i++) fac[i]=fac[i-1]*i%mod;
    inv[60]=qpow(fac[60],mod-2);
    for(int i=60-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--) subtask();
    return 0;
}