bzoj 3453 tyvj 1858 XLkxc 拉格朗日插值

tyvj 1858 XLkxc

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 267 Solved: 130
[Submit][Status][Discuss]

Description

神犇LYD虐完HEOI之后给傻×XLk出了一题：
SHY是某国的公主，平时的一大爱好是读诗...(中间略)...结果mod p就可以了

简明题意
给定 k,a,n,d,p
f(i)=1^k+2^k+3^k+......+i^k
g(x)=f(1)+f(2)+f(3)+....+f(x)
求(g(a)+g(a+d)+g(a+2d)+......+g(a+nd))mod p

对于所有数据
1<=k<=123
0<=a,n,d<=123456789
p==1234567891

Input

第一行数据组数，(保证小于6)
以下每行四个整数 k,a,n,d

Output

每行一个结果。

Sample Input

5
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output

5
5
5
5
5

HINT

Source

这些是很明显的，因为这个就是需要求的东西。

然后接下来怎么处理是关键。

对我来说的话，应该是手足无措的，但是某些大佬将其作差，

对于g作k+3次差分后其项为0，所以说g是一个最高项为k+2次的多项式，

对于f 作k+5次差分后其项为0，所以说f 是一个最高项为k+4次的多项式

所以说，因为k不大，所以每次O（k^2）的时间求出g，前缀和一下就可以了

然后知道了f的点值后就可以再一次k^2的时间求出n的值

复杂度是Tk^3

第64行中求值的时候取模的可以将每一项都模p，这个应该可以理解

 1 #include<cstring>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<cmath>
 6 
 7 #define p 1234567891
 8 #define N 157
 9 #define ll long long
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;char ch=getchar();
14     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
15     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 
19 ll a,n,d,m,k;
20 ll s1[N],s2[N];
21 ll g[N],f[N],inv[N<<1];
22 
23 ll fast_pow(ll a,ll b)
24 {
25     ll ans=1;
26     while(b)
27     {
28         if (b&1) (ans*=a)%=p;
29         (a*=a)%=p;
30         b>>=1;
31     }
32     return ans;
33 }
34 inline ll Lagrange(ll *a,int n,ll pos)
35 {
36     if (pos<=n) return a[pos];
37     ll ans=0;
38     for (int i=1;i<=n;i++)
39     {
40         ll s1=1,s2=1;
41         for (int j=1;j<=n;j++)
42             if (i!=j)
43             {
44                 (s1*=(pos-j))%=p;
45                 (s2*=(i-j))%=p;
46             }
47         (ans+=a[i]*s1%p*fast_pow(s2,p-2))%=p;
48     }
49     return ans;
50 }
51 int main()
52 {
53     freopen("fzy.in","r",stdin);
54     freopen("fzy.out","w",stdout);
55     
56     int T=read();
57     while(T--)
58     {
59         k=read(),a=read(),n=read(),d=read();
60         for (int i=1;i<=k+3;i++) g[i]=fast_pow(i,k);
61         for (int i=2;i<=k+3;i++) (g[i]+=g[i-1])%=p;
62         for (int i=2;i<=k+3;i++) (g[i]+=g[i-1])%=p;
63         f[0]=Lagrange(g,k+3,a);
64         for (int i=1;i<=k+5;i++) f[i]=Lagrange(g,k+3,(i*d+a)%p),(f[i]+=f[i-1])%=p;
65         printf("%lld
",(Lagrange(f,k+5,n)+p)%p);
66     }
67 }