[噼昂!]我被卷飞了

\[\color{red}{\text{校长者,真神人也,左马桶,右永神,会执利笔破邪炁,何人当之?}} \\ \begin{array}{|} \hline \color{pink}{\text{The principal is really a god}} \\ \color{pink}{\text{with a closestool on the left and Yongshen on the right}} \\ \color{pink}{\text{holding a sharp pen to pierce the truth}} \\ \color{pink}{\text{Who can resist him? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{green}{\text{校長は本当に神であり、左側にトイレ、右側にヨンシェンがあり}} \\ \color{green}{\text{鋭いペンを持って真実を突き刺している。誰が彼に抵抗できるだろうか? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{lightblue}{\text{Le principal est vraiment un dieu}} \\ \color{lightblue}{\text{avec des toilettes à gauche et Yongshen à droite}} \\ \color{lightblue}{\text{tenant un stylo pointu pour percer la vérité}} \\ \color{lightblue}{\text{Qui peut lui résister ? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{purple}{\text{Der Direktor ist wirklich ein Gott}} \\ \color{purple}{\text{mit einer Toilette links und Yongshen rechts}} \\ \color{purple}{\text{der einen spitzen Stift hält}} \\ \color{purple}{\text{um die Wahrheit zu durchdringen.}} \\ \color{purple}{\text{Wer kann ihm widerstehen? }} \\ \hline \end{array} \\ \begin{array}{|} \hline \color{cyan}{\text{Principalis deus est, Yongshen a dextris cum latrina}} \\ \color{cyan}{\text{acuto stylo ad perforandum veritatem: quis resistet ei? }} \\ \hline \end{array} \\ \color{red}{\text{对曰:“无人,狗欲当之,还请赐教!”}} \\ \newcommand\bra[1]{\left({#1}\right)} \newcommand\Bra[1]{\left\{{#1}\right\}} \newcommand\dx[0]{\text{dx}} \newcommand\string[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \newcommand\down[2]{{#1}^{\underline{#2}}} \newcommand\ddiv[2]{\left\lfloor\frac{#1}{#2}\right\rfloor} \newcommand\udiv[2]{\left\lceil\frac{#1}{#2}\right\rceil} \newcommand\lcm[0]{\operatorname{lcm}} \newcommand\set[1]{\left\{{#1}\right\}} \newcommand\ceil[1]{\left\lceil{#1}\right\rceil} \newcommand\floor[1]{\left\lfloor{#1}\right\rfloor} \]


  写 \(230\) 挂成 \(30\),真的笑麻了。以后还是稳健一点。

Problem A. 按位或 / \(\mathcal{Or}\)

  先考察若没有 "被 \(3\) 整除" 这个性质怎么做。不难想到容斥,我们容斥至多哪些位置有 \(1\). 设 \(t\) 的 \(1\) 的数位个数为 \(c\),那么有下列容斥式子:

\[ans=\sum_{i=0}^c(-1)^{c-i}\bra{{c\choose i}2^c}^n \]

  接下来我们应当考察被 \(3\) 整除的性质:用 \(10\) 进制下被三整除的性质类比,不难发现:

\[2^{2k}\equiv 1\pmod 3\qquad2^{2k+1}\equiv -1\pmod 3 \]

  显然,此时一个数在二进制下,奇偶数位的地位是不等价的,因此我们把这两维分开考虑做容斥即可。设 \(t\) 的偶数位有 \(even\) 个 \(1\),奇数位有 \(odd\) 个 \(1\),那么最后的容斥就是:

\[ans=\sum_{i=0}^{odd}\sum_{j=0}^{even}(-1)^{odd+even-i-j}f^n(i,j) \]

  其中 \(f(i,j)\) 表示奇数位至多有 \(i\) 个,偶数位至多有 \(j\) 个的数字个数:

\[f(x,y)=\sum_{i=0}^x\sum_{j=0}^y[2i+j\equiv 0\pmod 3]{x\choose i}{y\choose j} \]

  时间复杂度 \(\mathcal O(\log^4t)\).

#include <bits/stdc++.h>
using namespace std;

namespace Elaina {

#define rep(i, l, r) for (int i = l, i##_end_ = r; i <= i##_end_; ++i)
#define drep(i, l, r) for (int i = l, i##_end_ = r; i >= i##_end_; --i)
#define fi first
#define se second
#define Endl putchar('\n')

    template<class T> inline T fab(T x) { return x < 0? -x: x; }
    template<class T> inline void getmax(T& x, const T& rhs) { x = max(x, rhs); }
    template<class T> inline void getmin(T& x, const T& rhs) { x = min(x, rhs); }
    
    using ll = long long;
    using ull = unsigned long long;
    using pii = pair<int, int>;

} // namespace Elaina
using namespace Elaina;

const int mod = 998244353;
const int logt = 60;
inline void Add(int& x, const int& rhs) { (x += rhs) >= mod? x -= mod: 0; }
inline int qkpow(int a, ll n) {
    int ret = 1;
    for (; n; n >>= 1, a = 1ll * a * a % mod)
        if (n & 1) ret = 1ll * ret * a % mod;
    return ret;
}

ll n, t;
int C[105][105], ecnt, ocnt;
inline void prelude() {
    C[0][0] = 1;
    for (int i = 1; i <= 100; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
}

inline int calc(int x, int y) {
    int ret = 0;
    for (int i = 0; i <= x; ++i) for (int j = 0; j <= y; ++j) {
        if (((i << 1) + j) % 3 == 0)
            Add(ret, 1ll * C[x][i] * C[y][j] % mod);
    }
    return ret;
}

signed main() {
    freopen("or.in", "r", stdin);
    freopen("or.out", "w", stdout);
    cin.tie(NULL) -> sync_with_stdio(false);
    prelude(); cin >> n >> t;
    for (int i = 0; i <= logt; ++i) if (t >> i & 1) (i & 1)? ++ocnt: ++ecnt;
    int ans = 0;
    for (int i = 0; i <= ocnt; ++i) for (int j = 0; j <= ecnt; ++j) {
        if((ocnt + ecnt - i - j) & 1)
            Add(ans, mod - 1ll * C[ocnt][i] * C[ecnt][j] % mod * qkpow(calc(i, j), n) % mod);
        else Add(ans, 1ll * C[ocnt][i] * C[ecnt][j] % mod * qkpow(calc(i, j), n) % mod);
    }
    printf("%d\n", ans % mod);
    return 0;
}

Problem B. 最短路径 / \(\mathcal {Tree}\)

  先不管期望,最后我们只需要乘上 \({m\choose k}^{-1}\pmod{p}\) 即可。那么我们现在的问题是:求从 \(m\) 个点中任意选择 \(k\) 个点,找到一条经过这 \(k\) 个点的最短路径,所有方案的最短路径的长度之和。

  我们应当先考察经过 \(k\) 个点的所谓 "最短路径" 的组成 —— 如果我们连要求什么都不知道,还做不做了。显然,原树上有一些边贡献了 \(2\) 次,有一些边 \(1\) 次,还有一些边根本没有贡献。而没有贡献的这些边身份很清楚 —— 他们没有在 \(k\) 个点构成的虚树上,那么出现一次和两次又是什么情况?我们不妨先走出一条从 \(u\) 开始,最后又回到 \(u\) 的路径(或者说环),那么,所有在虚树上的边都出现了两次,不过,显然我们最后是没有必要回到 \(u\) 的,我们可以去掉一条从 \(u\) 开始到某个点结束的路径,显然我们希望找最长的,这样总路径长可能最短。同理,这个环的端点不一定是 \(u\),可能是其他的点,因此,我们去掉的长度是:

\[\max_{u,v\in P} dis(u,v) \]

  这不就是虚树的直径吗?因此,我们可以给出这个 "最短路径" 的定义:

  对于一个点集 \(P(|P|=k)\),其最短路径的长度 \(L(P)\) 定义为:

\[L(P)=\sum_{u\in P}\sum_{v\in P}dis(u,v)-D(P) \]

  其中 \(D(P)=\max_{u,v\in P} dis(u,v)\),即 \(P\) 构成的虚树的直径。

  我们已经弄清楚我们想要求什么了,接下来就是怎么求这个东西。显然,如果你要直接维护似乎有点困难(至少得三维,维数就已经超过限制了),但是我们发现要减去的东西似乎是独立的,我们可以先把前面那一坨 —— 指带俩 \(\Sigma\) 的东西 —— 给算出来,然后减去后面的那一坨 \(D(P)\).

  前面那一坨就不说了,对于后面那一坨,我们可以枚举直径到底是哪俩点之间的路径,然后统计这一路径在哪些点集被作为直径。具体操作,我们可以枚举一个点对 \((u,v)\),然后一个点一个点地加入点集,加入时判断这个点和左右两点之间的距离即可,注意,若距离相同,则你需要堆点集也钦定一个偏序关系,以保证同一直径不会被反复计算。

#include <bits/stdc++.h>
using namespace std;

namespace Elaina {

#define rep(i, l, r) for (int i = l, i##_end_ = r; i <= i##_end_; ++i)
#define drep(i, l, r) for (int i = l, i##_end_ = r; i >= i##_end_; --i)
#define fi first
#define se second
#define Endl putchar('\n')

    template<class T> inline T fab(T x) { return x < 0? -x: x; }
    template<class T> inline T getmax(T x, const T& rhs) { x = max(x, rhs); }
    template<class T> inline T getmin(T x, const T& rhs) { x = min(x, rhs); }

    using ll = long long;

} // namespace Elaina
using namespace Elaina;

const int mod = 998244353;
const int maxn = 2000;
const int maxm = 300;
inline int qkpow(int a, int n) {
    int ret = 1;
    for (; n; n >>= 1, a = 1ll * a * a % mod)
        if (n & 1) ret = 1ll * ret * a % mod;
    return ret;
}
int fac[maxn + 5], ifac[maxn + 5], inv[maxn + 5];
inline void prelude() {
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;
    for (int i = 2; i <= maxn; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
    }
}
inline int C(int n, int m) {
    if (n < m || n < 0 || m < 0) return 0;
    return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int p[maxm + 5], n, m, K;
int id[maxn + 5];
bool iskey[maxn + 5];
vector<int> g[maxn + 5];

inline void input() {
    cin >> n >> m >> K;
    rep (i, 1, m) cin >> p[i], iskey[p[i]] = true, id[p[i]] = i;
    int u, v;
    rep (i, 1, n - 1) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
}

int dis[maxm + 5][maxn + 5];
void dfs(int u, int par, int rt, int d) {
    dis[rt][u] = d;
    for (int v: g[u]) if(v ^ par)
        dfs(v, u, rt, d + 1);
}

int cnt[maxn + 5];
void dfs2(int u, int par) {
    cnt[u] = iskey[u];
    for (int v: g[u]) if (v ^ par)
        dfs2(v, u), cnt[u] += cnt[v];
}

inline void calc() {
    int sum = 0; /** calculate the edge which would not be considered into the answer */
    rep (i, 1, m) rep (j, i + 1, m) {
        int qualified = 0, d = dis[i][p[j]];
        rep (k, 1, n) if (k != p[i] && k != p[j]) {
            if (!iskey[k]) continue;
            if (dis[i][k] > d || dis[j][k] > d) continue;
            if (dis[i][k] < d && dis[j][k] < d) ++qualified;
            else if (dis[i][k] == d) {
                // to avoid the same situation
                if (id[k] > j) ++qualified;
            }
            else if(dis[j][k] == d) {
                if (id[k] > i) ++qualified;
            }
        }
        sum = (sum + 1ll * C(qualified, K - 2) * d % mod) % mod;
    }
    int all = 0; dfs2(1, 0);
    for (int i = 2; i <= n; ++i)
        all = (0ll + all + C(m, K) + mod - C(cnt[i], K) + mod - C(m - cnt[i], K)) % mod;
    all = ((ll)all << 1) % mod;
    all = (0ll + all + mod - sum) % mod;
    all = 1ll * all * qkpow(C(m, K), mod - 2) % mod;
    printf("%d\n", all);
}

signed main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    prelude();
    input();
    rep (rt, 1, m) dfs(p[rt], 0, rt, 0);
    calc();
    return 0;
}

Problem C. 仙人掌 / \(\mathcal{Cactus}\)

  着实妙啊。考察行列式的性质,我们最后为每个点指定一条出边,最后整张图的构成只有可能有两种:两两匹配,或者是一个大环。如果是两两匹配,那么它对答案的贡献是乘上一个 \(-1\),如果是一个大环,那么它对答案的贡献就是 \((-1)^{siz-1}2\),其中 \(siz\) 表示这个环的大小,有 \(2\) 是因为大环可能存在两个方向。然后,我们就可以用这个东西来 \(\rm DP\),具体的 \(\rm DP\) 过程,可以考虑建出圆方树,对于每个点定义 \(f(i,0|1)\) 表示该点是否有匹配覆盖的所有方案的和,对于方点,它的定义是其父亲是否和环中的某个点匹配的所有方案之和。然后做 \(\rm DP\) 就行了,复杂度 \(\mathcal O(n)\). 不得不说,如果你对行列式有足够掌握,并且熟悉圆方树一类的东西,那么它就是圆方树 \(\rm DP\) 的板题。

#include <bits/stdc++.h>
using namespace std;

namespace Elaina {

#define rep(i, l, r) for (int i = l, i##_end_ = r; i <= i##_end_; ++i)
#define drep(i, l, r) for (int i = l, i##_end_ = r; i >= i##_end_; --i)
#define fi first
#define se second
#define Endl putchar('\n')

    template<class T> inline T fab(T x) { return x < 0? -x: x; }
    template<class T> inline T getmax(T x, const T& rhs) { x = max(x, rhs); }
    template<class T> inline T getmin(T x, const T& rhs) { x = min(x, rhs); }

    using ll = long long;

} // namespace Elaina
using namespace Elaina;

/**
 * @param MOD used for modulo
 * @param RT the primitive root of @p MOD
*/
template<int MOD, int RT> struct Mint {
    int val;
    static const int mod = MOD;
    Mint(ll v = 0) { val = int(-mod < v && v < mod? v: v % mod); if (val < 0) val += mod; }
    inline friend bool operator == (const Mint& a, const Mint& b) { return a.val == b.val; }
    inline friend bool operator != (const Mint& a, const Mint& b) { return !(a == b); }
    inline friend bool operator < (const Mint& a, const Mint& b) { return a.val < b.val; }
    inline friend bool operator > (const Mint& a, const Mint& b) { return a.val > b.val; }
    inline friend bool operator <= (const Mint& a, const Mint& b) { return a.val <= b.val; }
    inline friend bool operator >= (const Mint& a, const Mint& b) { return a.val >= b.val; }
    inline Mint& operator += (const Mint& rhs) { return (*this) = Mint((*this).val + rhs.val); }
    inline Mint& operator -= (const Mint& rhs) { return (*this) = Mint((*this).val - rhs.val); }
    inline Mint& operator *= (const Mint& rhs) { return (*this) = Mint(1ll * (*this).val * rhs.val); }
    inline Mint operator - () const { return Mint(-val); }
    inline Mint& operator ++ () { return (*this) = (*this) + 1; }
    inline Mint& operator -- () { return (*this) = (*this) - 1; }
    inline friend Mint operator + (Mint a, const Mint& b) { return a += b; }
    inline friend Mint operator - (Mint a, const Mint& b) { return a -= b; }
    inline friend Mint operator * (Mint a, const Mint& b) { return a *= b; }
    inline friend Mint qkpow(Mint a, ll n) {
        assert(n >= 0); Mint ret = 1;
        for (; n; n >>= 1, a *= a) if (n & 1) ret *= a;
        return ret;
    }
    inline friend Mint inverse(Mint a) { assert(a != 0); return qkpow(a, mod-2); }
};
using mint = Mint<993244853, 5>;

const int maxn = 1e5;

int n, m;
struct edge { int to, nxt; } e[maxn * 4 + 5];
int tail[maxn + 5], ecnt;
inline void add_edge(int u, int v) {
    e[ecnt] = edge{v, tail[u]}; tail[u] = ecnt++;
    e[ecnt] = edge{u, tail[v]}; tail[v] = ecnt++;
}

inline void input() {
    cin >> n >> m;
    memset(tail + 1, -1, n << 2);
    int u, v;
    rep (i, 1, m) {
        cin >> u >> v;
        add_edge(u, v);
    }
}

int dfn[maxn + 5], times, ncnt;
int fa[maxn + 5];
bool onCir[maxn + 5];
vector<int> g[maxn * 2 + 5];
void tarjan(int u, int par) {
    dfn[u] = ++times, fa[u] = par;
    for (int i = tail[u], v; ~i; i = e[i].nxt) if ((v = e[i].to) ^ par) {
        if (!dfn[v]) tarjan(v, u);
        else if (dfn[v] < dfn[u]) {
            int x = ++ncnt, cur = u;
            g[v].push_back(x);
            while (cur ^ v) {
                g[x].push_back(cur);
                onCir[cur] = true;
                cur = fa[cur];
            }
            
        }
    }
    if (!onCir[u]) g[fa[u]].push_back(u);
}
inline void buildtre() {
    ncnt = n;
    tarjan(1, 0);
}

mint f[maxn * 2 + 5][2];
inline void work(int x) {
    static mint dp[maxn * 2 + 5][2];
    int n = g[x].size();
    /** solve @b f[x][1] first */
    dp[0][0] = f[g[x][0]][0], dp[0][1] = f[g[x][0]][1];
    for (int i = 1; i < n; ++i) {
        int cur = g[x][i];
        dp[i][0] = dp[i - 1][0] * f[cur][0] - dp[i - 1][1] * f[cur][1];
        dp[i][1] = dp[i - 1][0] * f[cur][1];
    }
    f[x][1] = dp[n - 1][0];
    /** When there exists a match between @p x 's father & the last son */
    rep (_, 0, 1) {
        reverse(g[x].begin(), g[x].end());
        dp[0][0] = f[g[x][0]][0], dp[0][1] = f[g[x][0]][1];
        for (int i = 1; i < n; ++i) {
            int cur = g[x][i];
            dp[i][0] = dp[i - 1][0] * f[cur][0] - dp[i - 1][1] * f[cur][1];
            dp[i][1] = dp[i - 1][0] * f[cur][1];
        }
        f[x][0] -= dp[n - 1][1];
    }
    mint prod = 1;
    for (int v: g[x]) prod *= f[v][1];
    prod = 2 * prod * ((n & 1)? -1: 1);
    f[x][0] += prod;
}
void dfs(int u) {
    for (int v: g[u]) dfs(v);
    if (u <= n) { // on tree.
        f[u][1] = 1;
        for (int v: g[u]) {
            if (v <= n) { // simple tree edge.
                f[u][0] = f[u][0] * f[v][0] - f[u][1] * f[v][1];
                f[u][1] *= f[v][0];
            }
            else { // a square node.
                f[u][0] = f[u][0] * f[v][1] + f[u][1] * f[v][0];
                f[u][1] = f[u][1] * f[v][1];
            }
        }
    } else work(u);
}

signed main() {
    // freopen("cactus.in", "r", stdin);
    // freopen("cactus.out", "w", stdout);
    cin.tie(NULL) -> sync_with_stdio(false);
    input(); buildtre(); dfs(1);
    printf("%d\n", f[1][0].val);
    return 0;
}
上一篇:Effective C++ 第二章 构造/析构/赋值运算


下一篇:d中复制构造器与构造器