251013 模拟赛

T2

给定一个 01 串，一次操作是选择一个长度为 \(k\) 的区间进行 flip。多次询问，每次询问给定区间 \([l,r]\)，问最少几次操作可以把区间内全变成 \(0\)。操作必须完包含于区间，询问之间相互独立。

首先将序列差分，操作转化为对两个相距 \(k\) 的点进行 flip。不难发现模 \(k\) 不同余的下标之间是相互独立的，因此可以按模 \(k\) 的余数将序列划分为若干子序列，每个子序列都是一个 \(k=2\) 的子问题。子问题的答案显然是偶数项减奇数项，无解当且仅当某个子序列有奇数个 \(1\)。无解可以用异或哈希简单处理。

考虑如何统计答案，记 \(b_i\) 表示全局中 \(i\) 所在的子序列不超过 \(i\) 的部分，从右往左对 '1' 编号，奇数项加，偶数项减，最终的结果（\(b_i\) 显然可以从 \(b_{i-k}\) 转移）。再求得 \(s_i\) 表示 \(b_{i-k+1\sim i}\) 的区间和。处理询问时，先判掉无解，此时 \(s_r\) 和 \(s_{l-1}\) 中 \([1,l-1]\) 部分 '1' 的贡献都是相同的，直接差分就可以了。

以上都是赛时思路，现在说说如何处理边界。在 \([l+1,r]\) 范围内，当 \(d_i=1\) 时我们希望对这一位进行 flip 否则不希望。求答案时我们只关心这一位是否需要 flip 而本质不关心 \(d_i\)。因此当且仅当 \(a_l=1\) 时我们希望对 \(l\) flip，\(a_r=1\) 时我们希望对 \(r+1\) flip（都是对差分数组 flip）。要考虑差分数组的第 \(r+1\) 项是因为一次合法的操作可能影响到它。

因此答案在 \(s_r-s_{l-1}\) 的基础上，先根据 \(a_r\) 决定是否修改 \(r\) 所在同余类的贡献，然后根据 \(a_l\) 和 \(d_l\) 决定是否修改 \(l\) 所在同余类的贡献。这里由于已经判过无解，所以各种情况边界位置的负号都已经确定，所有无需大分讨。

代码

#include<iostream>
#include<random>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 2e6 + 10;

int n, k, q;
int a[N], a1[N], d[N];

ll b[N], s[N];
ull w[N], h[N];
mt19937_64 rng((random_device){}());

inline int lb(int l, int r) {
    return (l - r % k) / k * k + r % k;
}

int main() {

    freopen("oper.in", "r", stdin);
    freopen("oper.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++) {
        char c; cin >> c; a[i] = c == '1';
        a1[i] = a1[i - 1] + a[i];
    }
    for(int i = 1; i <= n; i++) d[i] = a[i] ^ a[i - 1];

    for(int i = 0; i < k; i++) w[i] = rng();
    for(int i = 1; i <= n; i++) {
        h[i] = h[i - 1] ^ (d[i] ? w[i % k] : 0);
    }
    for(int i = 1; i <= n; i++) {
        b[i] = (d[i] ? i / k - b[max(0, i - k)] : b[max(0, i - k)]);
    }
    for(int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + b[i];
    }
    for(int i = n; i >= k; i--) {
        s[i] -= s[i - k];
    }

    while(q--) {
        int l, r;
        cin >> l >> r;
        if(r - l + 1 < k) {
            if(a1[r] == a1[l - 1]) cout << 0 << '\n';
            else cout << -1 << '\n';
            continue;
        }
        if(h[r] ^ h[l] ^ (a[l] ? w[l % k] : 0) ^ (a[r] ? w[(r + 1) % k] : 0)) { cout << -1 << '\n'; continue; }
        cout << (s[r] - s[l - 1] + a[r] * ((r + 1) / k - 2 * b[r + 1 - k]) - (a[l] ^ d[l]) * (l / k - 2 * b[max(0, l - k)])) << '\n';
    }

    return 0;
}

T3

给定正整数 \(n\)，求将 \(n\) 分解为若干可重无序的 \(2\) 的整数次幂的方案数。

\(n\le 10^{18}\)

首先通过打表或者分析得到答案的递推式为 \(g(i)=g(i-1)+[i\bmod 2=0]g(i/2)\)。证明考虑分讨是否分解出至少一个 \(1\)。为了方便计算，不妨设 \(n\) 是偶数，然后令 \(g(i)\gets g(2i)\)，那么递推式变为 \(g(i)=g(i-1)+g(i/2)\)。

考虑如何求 \(g\)。发现 \(g(i-1)\) 非常麻烦，因为我们不可能在线的求出每个 \(g\)，因此将 \(g\) 差分，有递推式：\(f(n)=\sum_{i=0}^{n/2}f(i)\)。虽然和前面没有什么本质的区别，但我们可以记录 \(s_1\) 表示 \(f\) 的一阶前缀和，这样就有 \(f(n)=s_1(n/2)\)。

此时继续考虑 \(s_1(n)\) 怎么表示成什么只和 \(n/2\) 有关的式子：

\[ s_1(n)=\sum_{i=0}^{n}f(i)=\sum_{i=0}^{n}s_1(i/2)=2s_2(n/2)-[n\bmod 2=0]s_1(n/2) \]

发现 \(s_k(n)\) 最多用到 \(s_{k+1}(n/2)\)，因此只需要记录 \(k\) 不超过递归层数的 \(s_k(n)\) 即可。手推转移系数发现 \(s_k\) 的式子中有 \(O(k)\) 项，没有什么非常简洁的转移。注意到式子可以写成一种标准形式：

\[ s_k(n)=\sum_{i=0}^{k+1}a_{k,i}s_i(n/2)+[n\bmod 2=0]b_{k,i}s_i(n/2) \]

并且 \(a,b\) 之间的转移非常简单：

\[ 2a_{i,j}\to a_{i+1,j+1}\\ -a_{i,j}\to b_{i+1,j}\\ b_{i,j}\to a_{i+1,j+1} \]

时间复杂度 \(O(\log^2V+T\log^3V)\)。

代码

#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N = 66;
const int MOD = 1e9 + 7;

int T, n;
int pw2[70];

int a[N][N], b[N][N];

void calc(int n, vector<int> &f) {
    if(n == 0) {
        f.resize(N);
        for(int i = 0; i < N; i++) f[i] = 1;
        return;
    }
    calc(n / 2, f);
    vector<int> g = f;
    for(int i = 0; i < N; i++) {
        f[i] = 0;
        for(int j = 0; j < N; j++) (f[i] += MOD + a[i][j] * g[j] % MOD + MOD + (n % 2 == 0 ? b[i][j] * g[j] % MOD : 0)) %= MOD;
    }
}

signed main() {

    freopen("div.in", "r", stdin);
    freopen("div.out", "w", stdout);

    pw2[0] = 1;
    for(int i = 1; i < 70; i++) pw2[i] = pw2[i - 1] * 2 % MOD;

    a[0][1] = 1;
    for(int i = 0; i < N - 1; i++) {
        for(int j = 0; j < N - 1; j++) {
            (a[i + 1][j + 1] += 2 * a[i][j]) %= MOD;
            (b[i + 1][j] += MOD - a[i][j]) %= MOD;
            (a[i + 1][j + 1] += b[i][j]) %= MOD;
        }
    }

    vector<int> f;
    cin >> T;
    while(T--) {
        cin >> n;
        calc(n, f);
        cout << f[0] << '\n';
    }

    return 0;
}

T4

给定两棵无根树 \(S,T\)，记 \(S\) 节点度数的最大值为 \(d\)。你需要进行至少一次，至多 \(d\) 次操作，将 \(T\) 变成 \(S\)。一次操作是把 \(T\) 替换为它的任意一棵点分树。

有根树 \(S\) 是 \(T\) 的一棵点分树当且仅当对于任意 \(S\) 中的一对父子 \(u=fa[v]\)，都有 \(u\) 向 \(S\) 的 \(v\) 子树中的至少一个点在 \(T\) 中连边。（显然这就是经典点分树的定义，“至少一个”总是恰好一个）

\(n\le 10^5,~n\times d\le 2\times 10^5\)

部分分：\(d=2\)

考虑 \(d=2\) 怎么做，我们需要将一棵任意的树在 \(2\) 步之内变为一条任意排列的链。不妨将点按照链的顺序进行重标号。发现并不是所有树都能一次成功，考虑构造一种中间体。考虑到链的大部分节点都只有一个儿子，而这样的点在原树上只能是连通块的叶子节点，因此考虑每次剥离一个叶子，将它追加到链的末尾。此时就会遇到一个问题：我们想要的节点不是叶子。

此时，我们只需要每次选择连通块中点权最大的点作为分治中心，先用一次操作建一棵点分树，就一定可以保证每次点权最小的节点是叶子。这样我们就解决了 \(d=2\)。建树可以考虑 kruskal 重构树，按点权从小到达加入节点，将它作为当前连通块的根。

考虑如何把链变成 \(S\)。我们还剩 \(d-2\) 次操作，这启发我们每次操作都将度数的 max 升高 \(1\)。由于正着不好考虑，尝试每次操作对 \(S\) 进行变换。一次变换我们可以把 \(S\) 的一条树边的下端点移动到子树中的任意一个点。尝试用这个操作将一个度数取到最大值的节点 \(u\) 的度数减少 \(1\)。注意到修改 \(u\to v\) 的边不能改变它的度数，修改其他的边指向 \(u\) 也不能使它的度数减小，因此想到将 \(fa[u]\to u\) 的边改到某一棵子树内。同时为了不对原本节点造成其它影响，可以选择一个叶子。

通过数学归纳法可以证明任意一棵子树的叶子节点总是比非叶子节点多一个。因此根据霍尔定理，总存在非叶子向子树内叶子的完美匹配。同时为了保证度数最大的节点也存在 \(fa\)，我们可以选择一个叶子作为初始的根。

记得特判 \(n=2\)。

代码

#include<iostream>
#include<vector>
#include<cassert>
#include<vector>
using namespace std;
const int N = 1e5 + 10;

vector<int> g1[N], g2[N];
vector<int> t[N];
int n, d;
int f[N], swp[N];

vector<vector<int>> ans;

int cur;
void dfs(int u, int fa, int &leaf) {
    f[u] = fa;
    if(g1[u].size() == 1 && fa) {
        g2[fa].push_back(u), g2[u].push_back(fa);
        return leaf = u, void();
    }
    int leaf2 = 0;
    for(int v : g1[u]) {
        if(v == fa) continue;
        int l = 0;
        dfs(v, u, l);
        if(!leaf) leaf = l;
        else leaf2 = l;
    }
    if(g1[u].size() > cur) {
        assert(fa);
        g2[fa].push_back(leaf2), g2[leaf2].push_back(fa);
    } else {
        if(fa) g2[fa].push_back(u), g2[u].push_back(fa);
    }
}

int fa[N], vis[N];
int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); }

int main() {

    cin >> n >> d;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g1[u].push_back(v);
        g1[v].push_back(u);
    }
    if(n == 2) {
        cout << 1 << '\n';
        cout << "0 1\n";
        return 0;
    }

    int pre = 0;
    for(int i = 1; i <= n; i++) {
        if(g1[i].size() == 1) { pre = i; break; }
    }
    for(int i = 1; i <= d - 2; i++) {
        cur = d - i;
        dfs(pre, 0, pre);
        ans.push_back(vector<int>(f, f + 1 + n));
        for(int j = 1; j <= n; j++) vector<int>().swap(g1[j]);
        for(int j = 1; j <= n; j++) swap(g1[j], g2[j]);
    }
    for(int i = 1; i <= n; i++) {
        if(g1[i].size() == 1) { pre = i; break; }
    }
    for(int i = pre, cnt = 0; i; ) {
        swp[++cnt] = i;
        if(i == pre) f[i] = 0;
        else f[i] = pre;
        if(g1[i][0] != pre) pre = i, i = g1[i][0];
        else if(g1[i].size() > 1) pre = i, i = g1[i][1];
        else i = 0;
    }

    ans.push_back(vector<int>(f, f + 1 + n));
    for(int i = 1; i <= n; i++) assert(g1[i].size() <= 2);

    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int ii = 1; ii <= n; ii++) {
        int i = swp[ii];
        vis[i] = 1;
        for(int v : t[i]) {
            if(!vis[v]) continue;
            f[find(v)] = i;
            fa[find(v)] = i;
        }
    }
    f[find(1)] = 0;

    ans.push_back(vector<int>(f, f + 1 + n));

    cout << ans.size() << '\n';
    for(int i = ans.size() - 1; i >= 0; i--) {
        for(int j = 1; j <= n; j++) cout << ans[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}