Polynomial
思路
题目给的是一个
n
n
n次多项式，要我们求
∑
i
=
l
r
\sum\limits_{i = l} ^{r}
i=l∑r，也就是一个累加的形式，容易想到转换成求前缀和。
所以我们考虑求前缀和，容易得到这个多项式的前缀和一定是
≥
n
&
≤
n
+
1
\geq n \& \leq n + 1
≥n&≤n+1次的多项式，
所以我们必须最少有
n
+
2
n + 2
n+2个前缀和才能推导，所以我们先通过
f
(
0
)
−
>
f
(
n
)
f(0) -> f(n)
f(0)−>f(n)得到
f
(
n
+
1
)
f(n + 1)
f(n+1)，
然后求个前缀和，再跑
m
m
m次拉个朗日插值得到
m
m
m组的询问。
由于这是一个
x
x
x连续取值的形式，所以我们可以预处理出前缀积，后缀积，以及阶乘逆元，然后即可
O
(
n
)
O(n)
O(n)求得答案。
代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int inf
= 0x3f3f3f3f;
const double eps
= 1e-7;
const int N
= 1e3 + 10, mod
= 9999991;
ll y
[N
], pre
[N
], suc
[N
], fac
[N
], inv
[N
], k
, m
;
ll
quick_pow(ll a
, int n
) {
ll ans
= 1;
while(n
) {
if(n
& 1) ans
= ans
* a
% mod
;
a
= a
* a
% mod
;
n
>>= 1;
}
return ans
;
}
ll
solve(ll n
) {
pre
[0] = suc
[k
+ 2] = 1;
for(int i
= 1; i
<= k
+ 1; i
++) {
pre
[i
] = 1ll * pre
[i
- 1] * (n
- i
) % mod
;
}
for(int i
= k
+ 1; i
>= 1; i
--) {
suc
[i
] = 1ll * suc
[i
+ 1] * (n
- i
) % mod
;
}
ll ans
= 0;
for(int i
= 1; i
<= k
+ 1; i
++) {
ll a
= 1ll * y
[i
] * pre
[i
- 1] % mod
* suc
[i
+ 1] % mod
, b
= 1ll * inv
[i
- 1] * inv
[k
+ 1 - i
] % mod
;
if((k
+ 1 - i
) & 1) b
*= -1;
ans
= (ans
+ 1ll * a
* b
% mod
+ mod
) % mod
;
}
return ans
;
}
int main() {
fac
[0] = inv
[0] = 1;
for(int i
= 1; i
< N
; i
++) {
fac
[i
] = 1ll * fac
[i
- 1] * i
% mod
;
}
inv
[N
- 1] = quick_pow(fac
[N
- 1], mod
- 2);
for(int i
= N
- 2; i
>= 1; i
--) {
inv
[i
] = inv
[i
+ 1] * (i
+ 1) % mod
;
}
int T
;
scanf("%d", &T
);
while(T
--) {
scanf("%lld %lld", &k
, &m
);
for(int i
= 1; i
<= k
+ 1; i
++) {
scanf("%lld", &y
[i
]);
}
y
[k
+ 2] = solve(k
+ 2);
k
++;
for(int i
= 1; i
<= k
+ 1; i
++) {
y
[i
] = (y
[i
] + y
[i
- 1]) % mod
;
}
for(int i
= 1; i
<= m
; i
++) {
int l
, r
;
scanf("%d %d", &l
, &r
);
printf("%lld\n",((solve(r
+ 1) - solve(l
)) % mod
+ mod
) % mod
);
}
}
return 0;
}
