传送门：https://nanti.jisuanke.com/t/40254
题意
$f(x)=a_0+a_1x+…+a_nx^n，没有给出a_0,a_1…a_n，只知道f(0),f(1)…f(n)，求$ $$\sum_{i=L}^Rf(i)\;\;mod\;\;9999991$$
思路
看到这个形式，就知道用拉格朗日插值法了，即
$$f[k]=\sum_{i=0}^ny_i\prod_{i\ne j}\frac{k-x[j]}{x[i]-x[j]}$$
但是题目中给出的点都是连续的，$(0,f(0))、(1,f(1))…(n,f(n))$，也就是x连续，所以插值式变为 $$f[k]=\sum_{i=0}^ny_i\prod_{i\ne j}\frac{k-j}{i-j}$$
所以一般的拉格朗日插值的复杂度为$O(n^2)$，而当x连续的时候，复杂度一度降为O(n)。
将上式展开：
$$f[k]=\sum_{i=0}^ny_i\frac{k(k-1)(k-2)…(k-n)}{[i(i-1)(i-2)…1]*[(-1)*(-2)*…*(i-n)]}$$
$$f[k]=\sum_{i=0}^ny_i\frac{\prod_{j=0}^{i-1}(k-j)\prod_{j=i+1}^n(k-j)}{i!*(i-n)!}$$
$$f[k]=\sum_{i=0}^ny_i\frac{pre[i-1]*suf[i+1]}{fac[i]*fac[n-i]}[(n-i) \&1 ?-1:1]$$
对于分母，可以预处理阶乘和阶乘逆元。 对于分子，做一个前缀积和一个后缀积。
所以首先，先插出一个f(n+1)，在对f进行一个前缀和sum数组，然后直接对sum数组进行插值，计算sum[R]-sum[l-1]即可。
注意：为什么要插出一个f(n+1)，是因为要先对sum数组有插值这个影响，而sum又是f的前缀和，所以要先插出一个f(n+1)来，所以也可以插f(n+2)、f(n+3)都可以，只要有这个影响就行。
Code
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
const int N = 1005;
const int MAXN = 1e7 + 10;
const ll mod = 9999991;
ll F[N];
ll pre[N], suf[N];
ll fac[N], invf[N];
ll sum[MAXN];
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void init() {
fac[0] = 1;
for(int i = 1;i < N; i++) fac[i] = fac[i - 1] * i % mod;
invf[N - 1] = quick_pow(fac[N - 1], mod - 2);
for(int i = N - 1;i >= 1; i--) invf[i - 1] = invf[i] * i % mod;
}
ll Lagrange(ll *f, int k, int n) {
if(k <= n) return f[k];
pre[0] = suf[n] = 1;
for(int i = 1;i <= n; i++) pre[i] = pre[i - 1] * (k - i + 1) % mod;
for(int i = n;i >= 1; i--) suf[i - 1] = suf[i] * (k - i) % mod;
ll ans = 0;
for(int i = 0;i <= n; i++) {
int opt = (n - i) & 1 ? -1 : 1;
ans = (ans + 1ll * opt * pre[i] % mod * suf[i] % mod * invf[i] % mod * invf[n - i] % mod * f[i] % mod + mod) % mod;
}
return f[k] = ans;
}
void solve()
{
init();
int T;
cin >> T;
while(T--) {
int n, q;
cin >> n >> q;
for (int i = 0; i <= n; i++) cin >> F[i];
F[n + 1] = Lagrange(F, n + 1, n);
sum[0] = F[0];
for (int i = 1; i <= n + 1; i++) sum[i] = (sum[i - 1] + F[i]) % mod;
while (q--) {
int l, r;
cin >> l >> r;
cout << (Lagrange(sum, r, n + 1) - Lagrange(sum, l - 1, n + 1) + mod) % mod << endl;
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/11/06/2019-icpc-nanchang-yaoqing-polnomial/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！