LOJ3120

52pts

\(N - D >= 2M\)或者\(M = 0\)那么就是\(D^{N}\)

只和数字的奇偶性有关，如果有k个奇数，那么必须满足\(N - k >= 2M\)

所以设\(f[i][j]\)表示第\(i\)个数有\(j\)个奇数的方案数，\(j\cdot f[i][j] \rightarrow f[i + 1][j - 1]\)和\((D - j) \cdot f[i][j] \rightarrow f[i + 1][j + 1]\)

64pts

这个只需要把上面的矩阵快速幂优化，只不过需要一点小技巧来卡一卡常……具体看代码吧

+8pts？

如果m = 1，不合法的只有每个数都不一样的情况

m = 2除去每个数都不一样的情况，有一个数大于1的情况且这个多少为2或3

以上就有72pts了！快落！

剩下的我就不会了，然后翻翻网上的题解写了一个容斥做法

至少k个方案数

奇数的序列的指数生成函数是

\(\frac{e^{x} - e^{-x}}{2} = \frac{x^{1}}{1!} + \frac{x^{3}}{3!} + \frac{x^{5}}{5!}....\)

至少有\(i\)个数为奇数的方案数

\(f_{i} = \binom{D}{i}n![x^{n}](\frac{e^{x} - e^{-x}}{2})^{i}e^{(D - i)x}\)

把\(2^{-i}\)提出去

\(f_{i} = \frac{\binom{D}{i}}{2^{i}} n!(e^{x} - e^{-x})^{i}e^{(D - i)x}\)

方案数是

然后把那个二项式展开一下

\(f_{i} = \frac{\binom{D}{i}}{2^{i}}n!e^{(D - i)x}\sum_{j = 0}^{i} (-1)^{j}e^{-jx}e^{(i - j)x}\binom{i}{j}[x^{n}]\)

合并一下就是

\(f_{i} = \frac{\binom{D}{i}}{2^{i}}n!\sum_{j = 0}^{i} (-1)^{j}e^{(D - 2j)x}\binom{i}{j}[x^{n}]\)

由于\(e^{ax}\)的第n项生成函数是\(\frac{a^{n}}{n!}\)

所以最后就是

\(f_{i} = \frac{i!\binom{D}{i}}{2^{i}}\sum_{j = 0}^{i} (-1)^{j}\frac{(D - 2j)^n}{j!(i - j)!}[x^{n}]\)

可以卷积算出来

然后

\(g_{i} = \sum_{j = i}^{D} (-1)^{j - i}\binom{i}{j}f_{j}\)

这个卷积一下也可以算

代码

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int, int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 2005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template <class T>

void read(T &res) {

    res = 0;

    T f = 1;

    char c = getchar();

    while (c < '0' || c > '9') {

        if (c == '-')

            f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template <class T>

void out(T x) {

    if (x < 0) {

        x = -x;

        putchar('-');

    }

    if (x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 998244353;

int D, N, M;

int fac[1000005], invfac[1000005];

int inc(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }

int mul(int a, int b) { return 1LL * a * b % MOD; }

int C(int n, int m) {

    if (n < m)

        return 0;

    return mul(fac[n], mul(invfac[m], invfac[n - m]));

}

void update(int &x, int y) { x = inc(x, y); }

int fpow(int x, int c) {

    int res = 1, t = x;

    while (c) {

        if (c & 1)

            res = mul(res, t);

        t = mul(t, t);

        c >>= 1;

    }

    return res;

}

namespace task1 {

int f[2][4005];

void Main() {

    int cur = 0;

    f[cur][0] = 1;

    for (int i = 1; i <= N; ++i) {

        memset(f[cur ^ 1], 0, sizeof(f[cur ^ 1]));

        for (int j = 0; j <= D; ++j) {

            if (j >= 1)

                update(f[cur ^ 1][j - 1], mul(f[cur][j], j));

            update(f[cur ^ 1][j + 1], mul(f[cur][j], D - j));

        }

        cur ^= 1;

    }

    int ans = 0;

    for (int i = 0; i <= D; ++i) {

        if (N - i >= 2 * M)

            update(ans, f[cur][i]);

    }

    out(ans);

    enter;

}

}  // namespace task1

namespace task2 {

vector<int> v1[305], v2[305];

struct Matrix {

    int f[305][305];

    Matrix() { memset(f, 0, sizeof(f)); }

    friend Matrix operator*(const Matrix &a, const Matrix &b) {

        Matrix c;

        for (int i = 0; i <= D; ++i) {

            v1[i].clear();

            v2[i].clear();

        }

        for (int i = 0; i <= D; ++i) {

            for (int j = 0; j <= D; ++j) {

                if (a.f[i][j])

                    v1[i].pb(j);

                if (b.f[i][j])

                    v2[i].pb(j);

            }

        }

        for (int i = 0; i <= D; ++i) {

            for (auto k : v1[i]) {

                for (auto j : v2[k]) {

                    update(c.f[i][j], mul(a.f[i][k], b.f[k][j]));

                }

            }

        }

        return c;

    }

} a, ans;

Matrix fpow(Matrix x, int c) {

    Matrix res = x, t = x;

    --c;

    while (c) {

        if (c & 1)

            res = res * t;

        t = t * t;

        c >>= 1;

    }

    return res;

}

void Main() {

    for (int i = 0; i <= D; ++i) {

        if (i >= 1)

            update(a.f[i][i - 1], i);

        update(a.f[i][i + 1], D - i);

    }

    ans = fpow(a, N);

    int res = 0;

    for (int i = 0; i <= D; ++i) {

        if (N - i >= 2 * M) {

            update(res, ans.f[0][i]);

        }

    }

    out(res);

    enter;

}

}  // namespace task2

namespace task3 {

const int MAXL = (1 << 20);

int W[MAXL + 5];

vector<int> a, b, f, g;

void NTT(vector<int> &p, int L, int on) {

    p.resize(L);

    for (int i = 1, j = L >> 1; i < L - 1; ++i) {

        if (i < j)

            swap(p[i], p[j]);

        int k = L >> 1;

        while (j >= k) {

            j -= k;

            k >>= 1;

        }

        j += k;

    }

    for (int h = 2; h <= L; h <<= 1) {

        int wn = W[(MAXL + on * MAXL / h) % MAXL];

        for (int k = 0; k < L; k += h) {

            int w = 1;

            for (int j = k; j < k + h / 2; ++j) {

                int u = p[j], t = mul(p[j + h / 2], w);

                p[j] = inc(u, t);

                p[j + h / 2] = inc(u, MOD - t);

                w = mul(w, wn);

            }

        }

    }

    if (on == -1) {

        int invL = fpow(L, MOD - 2);

        for (int i = 0; i < L; ++i) {

            p[i] = mul(p[i], invL);

        }

    }

}

vector<int> operator*(vector<int> a, vector<int> b) {

    vector<int> c;

    int t = a.size() + b.size() - 2, l = 1;

    while (l <= t) l <<= 1;

    c.resize(l);

    NTT(a, l, 1);

    NTT(b, l, 1);

    for (int i = 0; i < l; ++i) c[i] = mul(a[i], b[i]);

    NTT(c, l, -1);

    return c;

}

void Init() {

    W[0] = 1;

    W[1] = fpow(3, (MOD - 1) / MAXL);

    for (int i = 2; i < MAXL; ++i) W[i] = mul(W[i - 1], W[1]);

}

void Main() {

    Init();

    a.resize(D + 1);

    b.resize(D + 1);

    int t = 1;

    for (int i = 0; i <= D; ++i) {

        a[i] = mul(mul(t, fpow(inc(D, MOD - 2 * i), N)), invfac[i]);

        b[i] = invfac[i];

        t = mul(t, MOD - 1);

    }

    f = a * b;

    f.resize(D + 1);

    t = 1;

    for (int i = 0; i <= D; ++i) {

        f[i] = mul(f[i], fac[D]);

        f[i] = mul(f[i], invfac[D - i]);

        f[i] = mul(f[i], t);

        t = mul(t, (MOD + 1) / 2);

    }

    a.clear();

    a.resize(D + 1);

    t = 1;

    for (int i = 0; i <= D; ++i) {

        a[D - i] = mul(t, invfac[i]);

        f[i] = mul(f[i], fac[i]);

        t = mul(t, MOD - 1);

    }

    g = a * f;

    int L = N - 2 * M;

    int ans = 0;

    for (int i = 0; i <= L; ++i) {

        update(ans, mul(g[i + D], invfac[i]));

    }

    out(ans);

    enter;

}

}  // namespace task3

int main() {

#ifdef ivorysi

    freopen("f1.in", "r", stdin);

#endif

    fac[0] = 1;

    for (int i = 1; i <= 1000000; ++i) fac[i] = mul(fac[i - 1], i);

    invfac[1000000] = fpow(fac[1000000], MOD - 2);

    for (int i = 999999; i >= 0; --i) invfac[i] = mul(invfac[i + 1], i + 1);

    read(D);

    read(N);

    read(M);

    if (N - D >= 2 * M || M == 0) {

        out(fpow(D, N));

        enter;

    } else if (N <= 4000)

        task1::Main();

    else if (D <= 300)

        task2::Main();

    else if (M == 1) {

        int ans = fpow(D, N);

        if (D >= N) {

            update(ans, MOD - mul(fac[D], invfac[D - N]));

        }

        out(ans);

        enter;

    } else if (M == 2) {

        int ans = fpow(D, N);

        if (D >= N) {

            update(ans, MOD - mul(fac[D], invfac[D - N]));

        }

        for (int j = 2; j <= 3; ++j) {

            if (N - j <= D - 1) {

                int t = mul(D, C(D - 1, N - j));

                update(ans, MOD - mul(mul(t, invfac[j]), fac[N]));

            }

        }

        out(ans);

        enter;

    } else {

        task3::Main();

    }

    return 0;

}

巴特西

【LOJ】#3120. 「CTS2019 | CTSC2019」珍珠

LOJ3120

52pts

64pts

+8pts？

代码

最新文章

热门文章