专栏文章

CF 2127F Hamed and AghaBalaSar

rrizynvu
CF2127F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvh2bc
此快照首次捕获于
2025/12/02 09:01
3 个月前
此快照最后确认于
2025/12/02 09:01
3 个月前
查看原文
cnblogs。
首先考虑这个 f(a)f(a) 是什么。
发现跳（仅限第一个操作）的时候形如 x→nxt(x)→nxt(nxt(x))→⋯x\to nxt(x)\to nxt(nxt(x))\to \cdots，贡献就为 (anxt(x)−ax)+(anxt(nxt(x))−anxt(x))(a_{nxt(x)} - a_x) + (a_{nxt(nxt(x))} - a_{nxt(x)})。
于是在抵消之后，如果 xx 最终跳到了 yy，那么贡献就是 ay−axa_y - a_x。
然后会发现在给定了 an=max⁡{a1,a2,⋯ ,an}a_n = \max\{a_1, a_2, \cdots, a_n\} 的情况下，最后跳到的 yy 一定是离 xx 最近的 ay=ana_y = a_n 的 yy，然后若 y+1<ny + 1 < n 就会从 y+1y + 1 继续跳下去。
于是可以写出 f(a)f(a) 的表达式：an∑i=1n[ai=an]−∑i=2nai[ai−1=an]−a1a_n\sum\limits_{i = 1}^n[a_i = a_n] - \sum\limits_{i = 2}^n a_i[a_{i -1} = a_n] - a_1。
接下来考虑计数。
观察到 f(a)f(a) 的表达式与 ana_n，也就是最大值有关，并且整个序列都受最大值的限制。
于是先尝试在外层枚举 an=mxa_n = mx。
此时尝试分开计算两部分的贡献：
  1. an∑i=1n[ai=an]a_n\sum\limits_{i = 1}^n [a_i = a_n]。
  2. ∑i=2nai[ai−1=an]+a1\sum\limits_{i = 2}^n a_i[a_{i - 1} = a_n] + a_1。
首先考虑第 11 部分，ana_n 因为是枚举的可以抛开不看。
那么这个时候就可以把 ∑\sum 拆开转为对每个 ii 计算，会发现有 22 种情况：
  1. i=ni = n，这是因为 ana_n 的值是固定的，而其他的值不是。
  2. 1≤i<n1\le i < n。
对于第 11 种情况，发现此时就需要解决一个问题：
计算 f(n,m,mx)f(n, m, mx) 代表长度为 nn，值域为 [0,mx][0, mx]，和为 mm 的序列数量。
对此并没有什么好求的做法，于是只能考虑容斥 >mx> mx 的数的数量，可以得到：
f(n,m,mx)=∑i=0n(−1)i(ni)(m−i(mx+1)+n−1n−1)f(n, m, mx) = \displaystyle\sum\limits_{i = 0}^n (-1)^i\dbinom{n}{i}\dbinom{m - i(mx + 1) + n - 1}{n - 1}。
看似好像求解就需要 O(n)\mathcal{O}(n) 的复杂度，但是实际上只有 i(mx+1)≤mi(mx + 1)\le m 的 ii 是有用的，所以复杂度是 O(min⁡{n,mmx})\mathcal{O}(\min\{n, \frac{m}{mx}\})。
那么正好 mxmx 是从 11 到 nn 的，总复杂度就是 O(mln⁡m)\mathcal{O}(m\ln m)，看样子就很有道理。
第 11 种情况的方案数就为 f(n−1,m−mx,mx)f(n - 1, m - mx, mx)。
然后来考虑第 22 种情况。
因为每个元素只关心是不是 =mx= mx，所以能够发现 1∼n−11\sim n - 1 这 n−1n - 1 个位置的情况是同样的，那么就只需要求出一个下标的值再乘上 (n−1)(n - 1) 就可以了。
单个下标是好算的，相当于此时的限制是 ai=an=mxa_i = a_n = mx，那么方案数就为 f(n−2,m−2mx,mx)f(n - 2, m - 2mx, mx)。
于是第 22 种情况的方案数就为 f(n−2,m−2mx,mx)f(n - 2, m - 2mx, mx)。
接下来来考虑第 22 部分。
一样的尝试分讨，分为以下 33 种情况：
  • i=1i = 1。
  • 1<i<n1 < i < n。
  • i=ni = n。
对于第 11 种情况，如果要枚举 a1a_1 的值复杂度就爆掉了，于是尝试其他的做法。
考虑 f(n−1,m−mx,mx)f(n - 1, m - mx, mx) 种合法的 a1∼an−1a_1\sim a_{n - 1} 的方案，这 n−1n - 1 个元素的和都为 m−mxm - mx。
又因为这 n−1n - 1 个元素是平等的，所以期望下应当有 a1=m−mxn−1a_1 = \frac{m - mx}{n - 1}。
或者说，也可以考虑一个合法的 a1∼an−1a_1\sim a_{n - 1} 的方案，考虑把其所有排列（根据值相同定义排列相同），那么每个位置在所有排列中的对应值的和应当是相等的，对所有等价类分析，就可以得到这个结果。
于是对应的答案就为 f(n−1,m−mx,mx)×m−mxn−1f(n - 1, m - mx, mx)\times \frac{m - mx}{n -1}。
对于第 22 种情况，依然是只考虑一个元素，最后乘上 n−2n - 2。
对于一个元素，那就是要求 ai−1=an=mxa_{i - 1} = a_n = mx。
于是答案就是 f(n−2,m−2mx,mx)×(n−2)×m−2mxn−2f(n - 2, m - 2mx, mx)\times (n - 2)\times \frac{m - 2mx}{n - 2}。
对于第 33 种情况，那就是要求 an−1=an=mxa_{n - 1} = a_n = mx。
于是答案是 f(n−2,m−2mx,mx)×mxf(n - 2, m - 2mx, mx)\times mx。
最后的时间复杂度为 O(mln⁡m+log⁡mod⁡)\mathcal{O}(m\ln m + \log \operatorname{mod})。
其实在 n=2n = 2 的时候应该判一下第 22 部分的第 22 情况的，因为会涉及到除 00，不过因为本身会乘上 n−2=0n - 2 = 0 所以其实随便乘上一个不对的数也没什么问题。
C
#include <bits/stdc++.h>

using ll = long long;

constexpr ll mod = 1000000007;
constexpr int N = 4e5;

inline ll qpow(ll a, ll b) {
    ll v = 1;
    for (; b; b >>= 1, a = a * a % mod) {
        if (b & 1) {
            v = v * a % mod;
        }
    }
    return v;
}

ll fac[N + 1], ifac[N + 1];
inline void init() {
    for (int i = fac[0] = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[N] = qpow(fac[N], mod - 2);
    for (int i = N; i >= 1; i--) {
        ifac[i - 1] = ifac[i] * i % mod;
    }
}


inline ll C(int n, int m) {
    return n < m || m < 0 ? 0ll : (fac[n] * ifac[n - m] % mod * ifac[m] % mod);
}
inline ll f(int n, int m, int mx) {
    if (m < 0) {
        return 0;
    }
    if (n == 0) {
        return m == 0;
    }
    ll ans = 0;
    for (int i = 0; i * (mx + 1) <= m && i <= n; i++) {
        ll res = C(n, i) * C(m - i * (mx + 1) + n - 1, n - 1) % mod;
        ans = (ans + mod + (i & 1 ? -res : res)) % mod;
    }
    return ans;
}

inline void solve() {
    int n, m;
    scanf("%d%d", &n, &m);
    ll inv1 = qpow(n - 1, mod - 2), inv2 = qpow(n - 2, mod - 2);
    ll ans = 0;
    for (int mx = 0; mx <= m; mx++) {
        ll x1 = f(n - 1, m - mx, mx) * mx % mod;
        ll x2 = f(n - 2, m - mx * 2, mx) * (n - 1) % mod * mx % mod;
        ll y1 = f(n - 1, m - mx, mx) * (m - mx) % mod * inv1 % mod;
        ll y2 = f(n - 2, m - mx * 2, mx) * (n - 2) % mod * (m - mx * 2) % mod * inv2 % mod;
        ll y3 = f(n - 2, m - mx * 2, mx) * mx % mod;
        ans = (ans + x1 + x2 - y1 - y2 - y3 + mod * 3) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    init();
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...