【考试记录】4.8 Table ( 数论数学 --组合数 & 杨辉三角)

陆陆续续的开始考很多的试，也会更新这些题目记录下来，免得做完了之后毫无印象，就这么水过去了（以前的考试都是如此，哎……）

Table (T1) :

样例：

 

　　出于对数学题本能的恐惧考场上放弃了此题专攻T2 T3....事实证明其实这题是可做的。

　　我们发现其实这个图形就是一个广义上的杨辉三角：C（i, j） = a *  C （i - 1, j）+ b * C （i - 1, j - 1）; 我们可以形成一个最暴力的想法：通过第p行的数据暴力推算出其他行的数据，打成表格后输出。但我们分析这样做的本质：将每一个格子的贡献层层下传 / 上析，最后传到我们所需要查询的（x,y）格子上。所以我们联想到：如果能够直接计算出第p行上每一个格子对所求（x,y）的贡献，不就能够算出来了吗？

　　下面：

下面写一点点自己最开始看的时候没有太懂/没注意到的地方：

　　1：向右走：C(i, j) = C(i - 1, j - 1) + C(i - 1, j); C(i - 1, j) = C(i - 1, j - 1) - C(i, j); 所以对一个节点产生贡献的点即为它左侧&下方的点。

　　2：a非常的大，所以不能用快速幂计算出a后再取逆元，应处理出powa & powb数组。

　　3：处理组合数时，注意到因为n & m 有一个是不变的，所以可以快速线性递推求解。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 10100100
#define int long long
#define mod 998244353
int m, n, a, b, p, q, f[200000];
int invc[maxn], inv[maxn], powa[maxn], powb[maxn];
int inva[maxn], C[maxn];
bool flag = 0;

int read()
{
    int x = 0, k = 1;
    char c;
    c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

int poww(int x, int t)
{
    int base = 1;
    for(; t; t >>= 1, x = (x * x) % mod)
        if(t & 1) base = (base) * x % mod;
    return base;
}

void pre()
{
    inv[0] = inv[1] = 1;
    for(int i = 2; i < maxn; i ++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    inva[1] = poww(a, mod - 2), powa[0] = powb[0] = 1;
    powa[1] = a, powb[1] = b;
    for(int i = 2; i < maxn; i ++)
    {
        inva[i] = inva[i - 1] * inva[1] % mod;
        powa[i] = powa[i - 1] * a % mod;
        powb[i] = powb[i - 1] * b % mod;
    }
}

void work1(int x, int y)
{
    int lim = min(x - p, y - 1), ret = 0; C[0] = 1;
    for(int i = 1; i <= lim; i ++)
        C[i] = C[i - 1] * (x - p - i + 1) % mod * inv[i] % mod;
    for(int i = 0; i <= lim; i ++)
    {
        int tem = f[y - i] * powb[i] % mod;
        tem = (tem * powa[x - p - i]) % mod * C[i] % mod;
        ret = (ret + tem) % mod;
    }
    printf("%lld\n", (ret + mod) % mod);
}

void work2(int x, int y)
{
    int ret = 0, k = p - x + y; C[p - x - 1] = 1;
    for(int i = p - x; i <= k - 2; i ++)
        C[i] = C[i - 1] * i % mod * inv[i - p + x + 1] % mod;
    for(int i = 1; i <= y; i ++)
    {
        int tem = f[i] * poww(- b, y - i) % mod;
        tem = tem * C[k - i - 1] % mod;
        tem = tem * inva[k - i] % mod;
        ret = (ret + tem) % mod;
    }
    printf("%lld\n", (ret + mod) % mod);
}

signed main()
{
    freopen("table.in","r",stdin);
    freopen("table.out","w",stdout);
    m = read(), n = read(), a = read(), b = read();
    p = read(), q = read();
    pre();
    for(int i = 1; i <= n; i ++) f[i] = read();
    for(int i = 1; i <= q; i ++)
    {
        int x = read(), y = read();
        if(x == p) printf("%lld\n", f[y]);
        else if(x > p) work1(x, y);
        else work2(x, y);
    }
    return 0; 
}