LOJ3160 "NOI2019" Douzhudi

correct

After thinking about it for a long time, I found that I didn't even think of the first step... I turned over the problem and found that people didn't bother to talk about this step...

That is, after shuffling the cards, the probability of occurrence of each possible solution is the same.

why……

Starting from the initial state, the probability of a final state is multiplied by the probability of a number of steps. Looking at the denominator, it is \(n!\); looking at the numerator, it is \(A_i!(n-A_i)!\), so it is proved that the probability is\(\frac{1}{\binom{n}{A_i} }\).

Of course, there is a statement of combination meaning: because the internal order of the two piles is fixed, there is no difference between them. Then it is equivalent to having \(n\) balls, \(A_i\) black balls\(n-A_i\) white balls, one randomly taken out each time. The resulting arrangement corresponds to the original model one-to-one.

Next is a conclusion: \(E_i(x)\) represents the expectation of the value at the position of \(x\) after \(i\) operations, which can be expressed in the form of a quadratic polynomial about \(x\) .

After knowing this conclusion, push from \(E_{i-1}(x)\) to \(E_i(x)\), just take three random values ​​and bring them into \(E_i(x)\) to calculate, calculate After interpolation, you can get its polynomial coefficients.

After the practice is finished, the next step is to prove:

Consider induction:

Enumerate the probability of the ball at position \(x\) moving to position \(y\), so there are: \(\binom{n}{A_i} E_i(y)=\sum_{x=1}^{A_i }\binom{y-1}{x-1}\binom{n-y}{A_i-x}E_{i-1}(x)+\sum_{x=1}^{n-A_i}\binom{y -1}{x-1}\binom{n-y}{n-A_i-x}E_{i-1}(A_i+x)\)

We have to prove that this expression is a polynomial that is only related to \(y\). The following only considers the left side, and the other side is the same:

Since \(E_{i-1}(x)\) is a polynomial, it can be divided into several items and calculated separately. Direct ordinary polynomials may not be easy to calculate, so here is \(E_{i-1}(x)=\sum_{k=0}^2f_k(x-1)^{\underline k}\)

So we need to prove:\(\sum_{x=1}^{A_i}\binom{y-1}{x-1}\binom{n-y}{A_i-x}(x-1)^{\underline k} \) is a polynomial related to \(y\).

(Several steps are omitted here, students who want to push slowly push...)

See that this formula has nothing to do with \(x\), and is obviously related to the quadratic polynomial of \(y\). This is proved.

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10000010
#define M 500010
#define ll long long
#define mo 998244353
ll qpow(ll x, ll y = mo - 2) {
    ll r = 1;
    for (; y; y >>= 1, x = x * x % mo)
        if (y & 1)
            r = r * x % mo;
    return r;
}
int n, m, type;
int fac[N], ifac[N];
void initC(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % mo;
    ifac[n] = qpow(fac[n]);
    for (int i = n - 1; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % mo;
}
ll C(int m, int n) { return (ll)fac[m] * ifac[n] % mo * ifac[m - n] % mo; }
ll f0, f1, f2;
ll dot(ll x) { return ((f2 * x + f1) % mo * x + f0) % mo; }
void cha_1n2(ll y1, ll yn, ll y2) {
    static ll z1 = qpow(n - 1), zn = qpow((ll)(n - 1) * (n - 2) % mo), z2 = mo - qpow(n - 2);
    y1 = y1 * z1 % mo;
    yn = yn * zn % mo;
    y2 = y2 * z2 % mo;
    f0 = (y1 * n * 2 + yn * 2 + y2 * n) % mo;
    f1 = (mo - (y1 * (n + 2) + yn * 3 + y2 * (n + 1)) % mo) % mo;
    f2 = (y1 + yn + y2) % mo;
}
int main() {
    // freopen("in.txt","r",stdin);
    freopen("landlords.in", "r", stdin);
    freopen("landlords.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &type);
    initC(n);
    f0 = 0, f1 = (type == 1), f2 = (type == 2);
    for (int i = 1; i <= m; ++i) {
        int A;
        ll E1, En, E2;
        scanf("%d", &A);
        E1 = ((1 <= A ? C(n - 1, A - 1) * dot(1) : 0) + (1 <= n - A ? C(n - 1, n - A - 1) * dot(1 + A) : 0)) %
             mo;
        En = ((1 <= A ? C(n - 1, A - 1) * dot(A) : 0) + (1 <= n - A ? C(n - 1, n - A - 1) * dot(n) : 0)) % mo;
        E2 = ((1 <= A ? C(n - 2, A - 1) * dot(1) : 0) + (1 <= n - A ? C(n - 2, n - A - 1) * dot(1 + A) : 0) +
              (2 <= A ? C(n - 2, A - 2) * dot(2) : 0) + (2 <= n - A ? C(n - 2, n - A - 2) * dot(2 + A) : 0)) %
             mo;
        ll invC = (ll)ifac[n] * fac[n - A] % mo * fac[A] % mo;
        cha_1n2(E1 * invC % mo, En * invC % mo, E2 * invC % mo);
    }
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int x;
        scanf("%d", &x);
        printf("%lld\n", dot(x));
    }
    return 0;
}