洛谷 P4351 [CERC2015]Frightful Formula 题解

· · 题解

一、题目：

洛谷原题

codeforces原题

二、思路：

一道数学题。

先不管公式中的常数项 c，首先考虑第一行和第一列的贡献。

对于位于 (i,1) 的数 x，它的贡献为：\dbinom{2n - i-2}{n-i}\times a^{n-1}b^{n-i}x。

对于位于 (1,j) 的数 x，它的贡献为：\dbinom{2n-j-2}{n-j}\times a^{n-j}b^{n-1}x。

再来考虑常数项 c 的影响。我们可以发现，加入在位置 (i,j) 上加了一个常数 c，那么这个 c 最终就会“演变成”\dbinom{2n-i-j}{n-i}a^{n-j}b^{n-i}c。这种演变的思路也可以参见这道题。

关于为什么是这样的，我们可以这么考虑：假设一个人从 (i,j) 要走到 (n,n)，每向右走都要乘 a，向下走都要乘 b，那么乘 a 的次数和乘 b 的次数都是确定的。而又因为一共有 \dbinom{2n-i-j}{n-i} 种走法，所以最终的总贡献就是上面那个式子啦！

又因为 \forall 2\leq i,j\leq n，(i,j) 都要加上常数 c。所以它们的总贡献为 c\sum\limits_{i=2}^n\sum\limits_{j=2}^n\dbinom{2n-i-j}{n-i}b^{n-i}a^{n-j}。

考虑这个式子怎么进行化简。设 k=2n-i-j，更改枚举顺序，有：

\begin{aligned} \text{Original Formula} &= c\sum\limits_{k=0}^{2n-4}\left(\sum\limits_{i=\max\{0,k-n+2\}}^{\min\{k,n-2\}}\dbinom{k}{i}b^{i}a^{k-i} \right) \end{aligned}

将和式分为两部分。

第一部分：

\begin{aligned} \text{The First Part} &= c\sum\limits_{k=0}^{n-2}\sum\limits_{i=0}^k\dbinom{k}{i} b^i a^{k-i}\\ &= c\sum\limits_{k=0}^{n-2}(a+b)^k \end{aligned}

第二部分：

\begin{aligned} \text{The Second Part}&=c\sum\limits_{k=n-1}^{2n-4}\left(\sum\limits_{i=k-(n-2)}^{n-2} \dbinom{k}{i}b^i a^{k-i} \right)\\ &=c\sum\limits_{k=n-1}^{2n-4}f_k \end{aligned}

其中 f_k=\sum\limits_{i=k-(n-2)}^{n-2} \dbinom{k}{i}b^i a^{k-i} 。则根据组合数的递推公式，可以得到

f_k=(a+b)f_{k-1}-\dbinom{k-1}{k-n+1}b^{k-n+1}a^{n-1}-\dbinom{k-1}{n-2}b^{n-1}a^{k-n+1}

总时间复杂度：O(n)。

三、代码：

#include <iostream> // 目前是洛谷rk1
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
#define FILEIN(s) freopen(s, "r", stdin)
#define FILEOUT(s) freopen(s, "w", stdout)
#define mem(s, v) memset(s, v, sizeof s)

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

const int MAXN = 200005, MOD = 1000003;

int n, a, c, b;
long long factor[MAXN << 1], facinv[MAXN << 1], ans;
long long powa[MAXN], powb[MAXN], f[MAXN << 1];

inline long long power(long long a, long long b) {
    long long res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = 1LL * res * a % MOD;
        a = 1LL * a * a % MOD;
    }
    return res;
}

inline void prework(void) {
    factor[0] = 1;
    for (int i = 1; i <= 2 * n; ++ i) factor[i] = factor[i - 1] * i % MOD;
    facinv[2 * n] = power(factor[2 * n], MOD - 2);
    for (int i = 2 * n - 1; i >= 0; -- i) facinv[i] = facinv[i + 1] * (i + 1) % MOD;
    powa[0] = 1; powb[0] = 1;
    for (int i = 1; i <= n; ++ i)
        powa[i] = powa[i - 1] * a % MOD,
        powb[i] = powb[i - 1] * b % MOD;
}

inline long long C(int n, int m) {
    if (n < m) return 0;
    return factor[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}

inline long long get_f(int k) {
    long long res = 0;
    for (int i = k - (n - 2); i <= n - 2; ++ i)
        (res += C(k, i) * powb[i] % MOD * powa[k - i] % MOD) %= MOD;
    return res;
}

int main() {
    n = read(); a = read(); b = read(); c = read();
    prework();

    for (int i = 1; i <= n; ++ i) {
        long long x = read();
        if (i == 1) continue;
        long long tmp = C(2 * n - i - 2, n - i) * powa[n - 1] % MOD * powb[n - i] % MOD * x;
        (ans += tmp) %= MOD;
    }

    for (int j = 1; j <= n; ++ j) {
        long long x = read();
        if (j == 1) continue;
        long long tmp = C(2 * n - j - 2, n - j) * powa[n - j] % MOD * powb[n - 1] % MOD * x;
        (ans += tmp) %= MOD;
    }

    {
        long long tmp = 1;
        for (int k = 0; k <= n - 2; ++ k) {
            if (k != 0) tmp = tmp * (a + b) % MOD;
            (ans += c * tmp % MOD) %= MOD;
        }
    }

    f[n - 1] = get_f(n - 1);
    for (int k = n - 1; k <= 2 * n - 4; ++ k) {
        if (k != n - 1) {
            f[k] = (a + b) * f[k - 1] % MOD
                   - C(k - 1, k - n + 1) * powb[k - n + 1] % MOD * powa[n - 1] % MOD
                   - C(k - 1, n - 2) * powb[n - 1] % MOD * powa[k - n + 1] % MOD;
            f[k] %= MOD;
            if (f[k] < 0) f[k] += MOD;
        }
        (ans += c * f[k] % MOD) %= MOD;
    }

    printf("%lld\n", ans);
    return 0;
}