题目传送门

题目大意

给出,个询问，每个询问求

解题思路

很明显的拉格朗日插值
但是一直化简不出来
之后看题解发现了一个常识

之前也用过，但是死活想不起来，果然还是我太菜
有了这个常识这题就变得简单了，先插值求然后做前缀和

此时就变成了前缀和所表示的多项式的前项；

此时再插值求出来的就是前缀和的值了

即可

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);
        }
    }
}