深圳做网站排名哪家专业,百度公司好进吗,外包的优缺点,网站建设教程网哪个好Polynomial
思路
题目给的是一个nnn次多项式#xff0c;要我们求∑ilr\sum\limits_{i l} ^{r}il∑r#xff0c;也就是一个累加的形式#xff0c;容易想到转换成求前缀和。
所以我们考虑求前缀和#xff0c;容易得到这个多项式的前缀和一定是≥n≤n1\geq n \要我们求∑ilr\sum\limits_{i l} ^{r}il∑r也就是一个累加的形式容易想到转换成求前缀和。
所以我们考虑求前缀和容易得到这个多项式的前缀和一定是≥n≤n1\geq n \ \leq n 1≥n≤n1次的多项式
所以我们必须最少有n2n 2n2个前缀和才能推导所以我们先通过f(0)−f(n)f(0) - f(n)f(0)−f(n)得到f(n1)f(n 1)f(n1)
然后求个前缀和再跑mmm次拉个朗日插值得到mmm组的询问。
由于这是一个xxx连续取值的形式所以我们可以预处理出前缀积后缀积以及阶乘逆元然后即可O(n)O(n)O(n)求得答案。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.husing 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() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);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;
}
