题目传送门
题目大意
给出,
个询问,每个询问求
解题思路
很明显的拉格朗日插值
但是一直化简不出来
之后看题解发现了一个常识
之前也用过,但是死活想不起来,果然还是我太菜
有了这个常识这题就变得简单了,先插值求然后做前缀和
此时就变成了前缀和所表示的多项式的前
项;
此时再插值求出来的就是前缀和的值了
即可
AC代码
//#pragma GCC optimize(3,"Ofast","inline") #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <map> #include <set> #include <stack> #include <vector> #include <string> #include <iostream> #include <list> #include <cstdlib> #include <bitset> #include <assert.h> // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) // char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf; // #define int long long #define lowbit(x) (x & (-x)) #define lson root << 1, l, mid #define rson root << 1 | 1, mid + 1, r #define pb push_back typedef unsigned long long ull; typedef long long ll; typedef std::pair<ll, ll> pii; #define bug puts("BUG") const long long INF = 0x3f3f3f3f3f3f3f3fLL; const int inf = 0x3f3f3f3f; const int mod = 9999991; const double eps = 1e-6; template <class T> inline void read(T &x) { int sign = 1;char c = getchar();x = 0; while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();} while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();} x *= sign; } #ifdef LOCAL FILE* _INPUT=freopen("input.txt", "r", stdin); // FILE* _OUTPUT=freopen("output.txt", "w", stdout); #endif using namespace std; ll qmod(ll a,ll n) { ll ans = 1; while(n) { if(n&1) ans = ans * a % mod; a = a * a % mod; n >>= 1; } return ans; } const int maxn = 1e3 + 10; ll f[maxn]; ll pre[maxn]; ll suf[maxn]; ll fac[maxn], infac[maxn]; void init() { fac[0] = 1; for (int i = 1; i < maxn; ++i) { fac[i] = fac[i - 1] * i % mod; } infac[maxn - 1] = qmod(fac[maxn - 1], mod - 2); for (int i = maxn - 2; i >= 0; --i) { infac[i] = infac[i + 1] * (i + 1) % mod; } } ll cal(int n, int k) { pre[0] = 1; 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 res = 0; for (int i = 0; i <= n; ++i) { ll ret = f[i] * pre[i] % mod * suf[i] % mod * infac[i] % mod * infac[n - i] % mod; if((n-i)&1) res = (res - ret + mod) % mod; else res = (res + ret) % mod; } return res; } int main() { int t; int n, m; int l, r; init(); for (read(t); t--;) { read(n), read(m); for (int i = 0; i <= n; ++i) { read(f[i]); } f[n + 1] = cal(n, n + 1); for (int i = 1; i <= n + 1; ++i) (f[i] += f[i - 1]) %= mod; for (; m--;) { read(l), read(r); printf("%lld\n", (cal(n + 1, r) - cal(n + 1, l - 1) + mod) % mod); } } }