1 如果打表发现某个数列: 差分有限次之后全为0 例如: 2017新疆乌鲁木齐ICPC现场赛D题
1,
2,
4,
8,
16,
31,
57,
99,
163,
256,……
2 【2018江苏南京ICPC现场赛也有这样的题目】
3 那么可以使用以下黑科技计算出第k(1e18)项(对质数取模) (原理: 拉格朗日插值)
4 预处理复杂度为线性, 每次计算复杂度为: O(传入项数个数)【同样也是线性】
5 以下代码为内测版, 出锅了fold不背锅, 欢迎指出bug
6
7 ------------------------下面是模板代码------------------------
8 typedef
long long ll;
9
10 //mod一定要是质数
11 const int mod=1e9+
7;
12
13 int pv[]={
0,
1,
2,
4,
8,
16,
31,
57};
//前几项, 前面无效值用0占位
14 const int st=
1,ed=
6;
//使用上面数组下标为[st,ed]的数据
15
16 ll fac[ed+
5],inv[ed+
5],facinv[ed+
5];
17 ll pre[ed+
5],saf[ed+
5];
18
19 //预处理: fac[]阶乘, inv[]逆元, facinv[]阶乘逆元
20 //只需要main函数内调用一次!
21 void init()
22 {
23 fac[
0]=inv[
0]=facinv[
0]=
1;
24 fac[
1]=inv[
1]=facinv[
1]=
1;
25 for(
int i=
2;i<ed+
3;++
i)
26 {
27 fac[i]=fac[i-
1]*i%
mod;
28 inv[i]=mod-(mod/i*inv[mod%i]%
mod);
29 facinv[i]=facinv[i-
1]*inv[i]%
mod;
30 }
31 }
32
33
34 //计算第x0项的值
35 //复杂度O(ed-st)
36 ll cal(ll x0)
37 {
38 int n=ed-
st;
39 x0=((x0%mod)+mod)%
mod;
40 pre[
0]=((x0-st)%mod+mod)%
mod;
41 saf[n]=((x0-st-n)%mod+mod)%
mod;
42 for(
int i=
1;i<=n;++
i)
43 {
44 pre[i]=((pre[i-
1]*(x0-st-i))%mod+mod)%
mod;
45 saf[n-i]=((saf[n-i+
1]*(x0-st-n+i))%mod+mod)%
mod;
46 }
47 ll res=
0;
48 for(
int i=
0;i<=n;++
i)
49 {
50 ll fz=
1;
51 if(i!=
0)fz=fz*pre[i-
1]%
mod;
52 if(i!=n)fz=fz*saf[i+
1]%
mod;
53 ll fm=facinv[i]*facinv[n-i]%
mod;
54 if((n-i)&
1)fm=mod-
fm;
55 (res+=pv[i+st]*(fz*fm%mod)%mod)%=
mod;
56 }
57 return res;
58 }
View Code
fold爷nb
转载于:https://www.cnblogs.com/MekakuCityActor/p/10604280.html
相关资源：Fold算法实现最短路径
