DontKnowWhatToSay-JZTXT

[ABC306G] Return to 1

without sol:

???

\(10^{10^{100}}\) 大的离谱，只要凑出一条能回到1的路径，长度为 \(x = 2^{p_1} \times 5^{p_2}\)。

容易注意到该条件等价于所有从1出发后回到1的环的 \(\gcd = 2^{p_1} \times 5^{p_2}\)。

问题回到如何数环，如果极限构造至少有 \(\frac{m}{2}\) 个环，数不完。

how to deal with？

with sol:

\(|dep_u + 1 - dep_v|\)

[CF961G] Partitions

without sol:

容易想到一个柿子

\[ans = \sum_{i = 1}^{n} w_i \sum_{s = 1}^{n} s \binom{n - 1}{s - 1}{n - s\brace k - 1} \]

后面的部分拆出来

\[\sum_{s = 1}^{n} s \binom{n - 1}{s - 1}{n - s\brace k - 1} \]

带入斯特林数通项公式

\[\sum^n_{s = 1} s \binom{n - 1}{s - 1} \sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}t^{n - s}}{t!(k - t - 1)!} \]

后面的不太好做，但前面的形式挺不错的

\[\sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}}{t!(k - t - 1)!} \sum^n_{s = 1} s \binom{n - 1}{s - 1}t^{n - s} \]

\[\binom{n}{m} = \frac{n!}{m!(n - m)!} \]

\(s\) 和 \(s - 1\) 差 \(1\) 试着拼一下把 \(s\) 换出来

\[\sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}}{t!(k - t - 1)!} \sum^n_{s = 1}\left(\binom{n - 1}{s - 1}t^{n - s} + (s- 1) \binom{n - 1}{s - 1}t^{n - s}\right) \]

\[\sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}}{t!(k - t - 1)!} \left(\left(\sum^n_{s = 1}\binom{n - 1}{s - 1}t^{n - s}\right) + \left(\sum^n_{s = 1}(s- 1) \binom{n - 1}{s - 1}t^{n - s}\right)\right) \]

\[\sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}}{t!(k - t - 1)!} \left(\left(\sum^n_{s = 1}\binom{n - 1}{s - 1}t^{n - s}\right) + (n - 1)\left(\sum^n_{s = 1} \binom{n - 2}{s - 2}t^{n - s}\right)\right) \]

组合数不好算，但是幂好算，发现两个式子都是二项式定理的结构，配个 \(1\) 凑出来

\[\sum^{k - 1}_{t = 0}\frac{(-1)^{k - t - 1}}{t!(k - t - 1)!} \left((t + 1)^{n - 1} + (n - 1) (t + 1)^{n - 2}\right) \]

剩下的都很好算，幂次为负数时特判一下

code

ll Pow(ll a, ll b, ll mod) {
    if(b < 0) return Pow(Pow(a, -b, mod), mod - 2, mod);
    ll res = 1;
    while(b) {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return res;
}
const int mod = 1e9 + 7;
const int maxk = 2e5 + 10;
int n, k;
int sum;
int fac[maxk];
void Debug() {
#ifdef LOCAL
#endif
}
signed main() {
    n = read(), k = read();
    for(int i = 1; i <= n; i++) {
        int a = read();
        sum = (sum + a) % mod;
    }
    fac[0] = 1;
    for(int i = 1; i <= k; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    int ans = 0;
    for(int t = 0; t < k; t++) {
        if((k - t) & 1)  // 0
            ans = (ans + 1ll * Pow(1ll * fac[t] * fac[k - 1 - t] % mod, mod - 2, mod) * Pow(t + 1, n - 2, mod) % mod * (n + t) % mod) % mod;
        else
            ans = (ans - 1ll * Pow(1ll * fac[t] * fac[k - 1 - t] % mod, mod - 2, mod) * Pow(t + 1, n - 2, mod) % mod * (n + t) % mod + mod) % mod;
    }
    write(1ll * ans * sum % mod);
    return 0;
}

优秀的遇见单调队列维护难以撤销的信息，可以考虑过中点重构，均摊 \(O(n)\)。

奇怪的对于奇怪的环相关的特性尝试染色？ AT_agc006_f

不会的发现难以入手记得固定部分条件考虑。

分治的，定值的，背包求体积恰为的，使用分治背包。

选出 \(n，n = 2k\) 个物品，分成两个大小为 \(k\) 的部分，存在方案使得两边体积和之差的绝对值小于体积域 \(m\)。证：滑动窗口。

设 vector<int> Solve(int n, int L, int R) 函数，递归到 Solve(n / 2, (L - m) / 2, (R + m) / 2) 奇数则单独枚举一位。复杂度 \(O(m^2\log n)\)。

DMOPC '21 Contest 8 P5 - Tree Building

笨蛋的，点权最短路每个点只会被松弛一次