http://codeforces.com/problemset/problem/622/F 第一次写了一下插值。 插值法主要用于解决知道某函数是几次函数(不妨设次数为n)，并且可以很方便的计算出在这个函数上的n+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
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod=1e9+7;
long long kpow(long long a,long long b)
{
long long base = a,y = 1;
for(;b;b>>=1)
{
if(b&1) y = y*base%mod;
base = base*base%mod;
}
return y;
}
LL n,k;
LL y[1000010]={};
LL fz[1000010]={};
LL fm[1000010]={};
LL ans=0;
int main()
{
scanf("%I64d%I64d",&n,&k);
for(int i=1;i<=k+2;i++)
{
y[i]=y[i-1]+kpow(i,k);
y[i]%=mod;
}
if(n<=k+2)
{
cout<<y[n];
return 0;
}
fz[0]=1;
for(int i=1;i<=k+2;i++)
{
fz[i]=fz[i-1]*(n-i);
fz[i]%=mod;
}
fm[0]=1;
for(int i=1;i<=k+2;i++)
{
fm[i]=fm[i-1]*kpow(i,mod-2);
fm[i]%=mod;
}
for(int i=1;i<=k+2;i++)
{
LL o;
o=y[i]*fz[k+2];
if(o>=mod) o%=mod;
o*=kpow(n-i,mod-2);
if(o>=mod) o%=mod;
o*=fm[i-1];
if(o>=mod) o%=mod;
o*=fm[k+2-i];
if(o>=mod) o%=mod;
if((k+2-i)%2==1) o*=-1;
ans+=o;
if(abs(ans)>=abs(mod)) ans%=mod;
}
ans+=mod;
ans%=mod;
printf("%I64d",ans);
return 0;
}
|