【XJTU 2020暑期集训】Day1 - 2020 杭电多校训练第6场

A - Road To The 3rd Building

按区间长度对区间分组，分别计算每组区间对于答案的贡献。设该组区间的长度均为 L，考虑位置 i 被多少个区间覆盖，设为 a_i，发现序列 a_1\dots a_n 为 1,2,3\dots k-1,k,k\dots k,k,k-1\dots 3,2,1 的形式，要计算 \sum_{i=1}^n a_i，前面一段可以用二次后缀和计算得出，后面一段可以用二次前缀和计算得出，中间一段用该段区间和乘 k 即可。则该组区间对答案的贡献即为 \frac{1}{L}\sum_{i=1}^n a_i。总复杂度 O(n)

B - Little Rabbit's Equation

签到题，枚举进制数模拟即可。

C - Borrow

咕

D - Asteroid in Love

咕

E - Fragrant numbers

首先有一个明显的上界为 \lceil n/31\rceil，因为只能添加加号、乘号和括号，所以数字一定不会减少，并且一个循环节所能构成的最小数字为 1\times 1\times(4+5)+1\times 4+1\times 9+1\times 9=31，由此可得上界。

设 \mathrm{bool}\;f[i][l][r] 表示区间 [l,r] 能否表示出数字 i，由于可以添加加号、乘号和括号，有转移方程 f[x\oplus y][l][r]=f[x\oplus y][l][r]\vee (f[x][l][m]\wedge f[y][m+1][r])，其中 \oplus 为 + 或 \times，m 为分界点，x,y 分别为左右区间构成的数字，边界条件为 f[\mathrm{getnum}(i,j)][i][j]=\mathrm{true}，\mathrm{getnum}(i,j) 表示区间 [i,j] 所表示的数字，这样我们就得到了一个复杂度 O(n^5/31^3) 的dp。

小范围打表发现除了3和7无法构成之外，其余数字均能被构成且前缀长度均在10左右。大胆猜测对于任意的 n\le 5000 均能被长度小于15的前缀构成，于是将上界缩小至15，此时dp复杂度变为 O(n^2\cdot 15^3)。打表发现5000之内的数字除了3和7均能被长度不超过11的前缀构成，然后直接copy就行了。

F - A Very Easy Graph Problem

由于 2^1+2^2+\dots+2^{i-1}<2^i，所以如果从 x 可以经过 1\dots i-1 中的某些边到达 y，那么一定不会去走 i 这条边。所以按照边的顺序构建生成树，统计每条边两端各有多少个黑白节点，将答案加上 w_{x,y}\cdot(\mathrm{cnt}[x][0]\cdot\mathrm{cnt}[y][1]+\mathrm{cnt}[x][1]\cdot\mathrm{cnt}[y][0]) 即可。总复杂度 O(n)。

G - A Very Easy Math Problem

咕

H - Yukikaze and Smooth numbers

咕

I - Divisibility

有结论：当且仅当 b\equiv 1\pmod{x} 时原命题成立（原命题：对于任意 b 进制正整数 y=\overline{c_1c_2\dots c_n}，有 \sum_{i=1}^n c_i\equiv 0\pmod{x}\Longleftrightarrow y\equiv 0\pmod{x}）。证明如下：

当 b\equiv 1\pmod{x} 时，y\equiv c_1b^{n-1}+c_2b^{n-2}+\dots+c_nb^0\equiv\sum_{i=1}^n c_i\equiv 0\pmod{x}，原命题成立。

当 b\not\equiv 1\pmod{x} 时，假设原命题成立。若 x\le b，令 y=\overline{1(x-1)}=1\cdot b^1+(x-1)b^0，由原命题可得 y\equiv 0\pmod{x}，又因为 y\equiv b+x-1\equiv b-1\pmod{x}，所以 b\equiv 1\pmod{x}，这与 b\not\equiv 1\pmod{x} 矛盾，所以原命题不成立。若 x\gt b，令 y=x=\overline{c_1c_2\dots c_n}，显然有 \sum_{i=1}^n c_i\lt x，所以 \sum_{i=1}^n c_i\not\equiv 0\pmod{x}，由原命题可得 y\not\equiv 0\pmod{x}，这与 y=x 矛盾，所以原命题不成立。

J - Expectation

对于边权二进制拆位，分别统计每一位对于答案的贡献。先对原图跑一边矩阵树定理，计算出生成树的总个数 s。对于第 i 位，令所有边的边权都等于原来的第 i 位，此时只有边权全是1的生成树才会对答案产生贡献，所以选取所有边权为1的边，跑一遍矩阵树定理，记总数为 c_i，则第 i 位对总答案的贡献即为 \frac{c_i\cdot 2^i}{s}。总复杂度 O(n^3\log n)。

K - Kirakira

咕

Code

A - Road To The 3rd Building

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define MOD 1000000007
#define mod(x) ((x % MOD + MOD) % MOD)
#define inv(x) (fpow(x, MOD - 2))
#define int long long

using namespace std;

int T, n;
int a[MAX_N];
int p[MAX_N];
int s[MAX_N];
int pre[MAX_N];
int suf[MAX_N];

int fpow(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD, k >>= 1;
    }
    return ans;
}

int getsum(int l, int r) {
    if (l <= r) {
        return mod(p[r] - p[l - 1]);
    }
    return 0;
}

int getfront(int x) {
    if (x > 0) {
        return mod(suf[1] - suf[x + 1] - x * getsum(x + 1, n));
    }
    return 0;
}

int getback(int x) {
    if (x > 0) {
        return mod(pre[n] - pre[n - x] - x * getsum(1, n - x));
    }
    return 0;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", a + i);
        }
        for (int i = 1; i <= n; i++) {
            p[i] = mod(p[i - 1] + a[i]);
        }
        s[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            s[i] = mod(s[i + 1] + a[i]);
        }
        for (int i = 1; i <= n; i++) {
            pre[i] = mod(pre[i - 1] + p[i]);
        }
        suf[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            suf[i] = mod(suf[i + 1] + s[i]);
        }
        int up = 0, dn = 0;
        for (int i = 1; i <= n; i++) {
            int res = 0;
            if (i <= n - i + 1) {
                res = mod(res + getsum(i, n - i + 1) * i);
                res = mod(res + getfront(i - 1) + getback(i - 1));
            } else {
                res = mod(res + getsum(n - i + 1, i) * (n - i + 1));
                res = mod(res + getfront(n - i) + getback(n - i));
            }
            res = mod(res * inv(i));
            up = mod(up + res), dn = mod(dn + (n - i + 1));
        }
        printf("%lld\n", mod(up * inv(dn)));
    }
}

B - Little Rabbit's Equation

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define int long long

using namespace std;

string substr(const string &s, int l, int r) {
    if (l <= r) {
        return s.substr(l, r - l + 1);
    }
    return "";
}

int getd(char c) {
    if (isdigit(c)) {
        return c - '0';
    }
    return c - 'A' + 10;
}

int getnum(const string &s, int b) {
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        int d = getd(s[i]);
        if (d >= b) {
            return -1;
        }
        ans = ans * b + d;
    }
    return ans;
}

int calc(int a, int b, char op) {
    if (op == '+') {
        return a + b;
    }
    if (op == '-') {
        return a - b;
    }
    if (op == '*') {
        return a * b;
    }
    if (a % b == 0) {
        return a / b;
    }
    return -1;
}

void work(const string &s) {
    int poseq = s.find('=');
    string ls = substr(s, 0, poseq - 1);
    string rs = substr(s, poseq + 1, s.size() - 1);
    int posop = -1;
    char op = '?';
    for (int i = 0; i < ls.size(); i++) {
        if (ls[i] == '+' || ls[i] == '-' || ls[i] == '*' || ls[i] == '/') {
            posop = i, op = ls[i];
            break;
        }
    }
    string ls1 = substr(ls, 0, posop - 1);
    string ls2 = substr(ls, posop + 1, ls.size() - 1);
    for (int i = 2; i <= 16; i++) {
        int a = getnum(ls1, i);
        int b = getnum(ls2, i);
        int c = getnum(rs, i);
        if (a == -1 || b == -1 || c == -1) {
            continue;
        }
        if (calc(a, b, op) == c) {
            cout << i << endl;
            return;
        }
    }
    cout << "-1" << endl;
}

signed main() {
    string s;
    while (cin >> s) {
        work(s);
    }
}

E - Fragrant numbers

打表程序：

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 5005
#define MAX_R 20
#define UB 15

using namespace std;

const int L = 10;
const int D[] = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};

int n = 5000;
int ans[MAX_N];
bool f[MAX_N][MAX_R][MAX_R];

int getd(int x) {
    return D[(x - 1) % L];
}

int getnum(int l, int r) {
    int ans = 0;
    for (int i = l; i <= r; i++) {
        ans = ans * 10 + getd(i);
    }
    return ans;
}

int main() {
    for (int i = 1; i <= UB; i++) {
        for (int j = i; j <= UB; j++) {
            int x = getnum(i, j);
            if (x <= n) {
                f[x][i][j] = true;
            } else {
                break;
            }
        }
    }
    for (int len = 2; len <= UB; len++) {
        for (int l = 1, r = len; r <= UB; l++, r++) {
            for (int m = l; m < r; m++) {
                for (int x = 1; x <= n; x++) {
                    if (f[x][l][m]) {
                        for (int y = 1; y <= n; y++) {
                            if (f[y][m + 1][r]) {
                                if (x + y <= n) {
                                    f[x + y][l][r] = true;
                                }
                                if (x * y <= n) {
                                    f[x * y][l][r] = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ans[i] = -1;
        for (int j = 1; j <= UB; j++) {
            if (f[i][1][j]) {
                ans[i] = j;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d,", ans[i]);
    }
}

F - A Very Easy Graph Problem

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAX_N 100005
#define MOD 1000000007
#define int long long

using namespace std;

struct Edge {
    int t, w;
    Edge() {}
    Edge(int _t, int _w) : t(_t), w(_w) {}
};

int T, n, m, ans;
int a[MAX_N];
int par[MAX_N];
int cnt[MAX_N][2];
vector<Edge> e[MAX_N];

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

void merge(int x, int y) {
    par[find(x)] = find(y);
}

bool same(int x, int y) {
    return find(x) == find(y);
}

void dfs1(int x, int p) {
    cnt[x][a[x]]++;
    for (int i = 0; i < e[x].size(); i++) {
        int t = e[x][i].t;
        if (t != p) {
            dfs1(t, x);
            cnt[x][0] += cnt[t][0];
            cnt[x][1] += cnt[t][1];
        }
    }
}

void dfs2(int x, int p) {
    for (int i = 0; i < e[x].size(); i++) {
        int t = e[x][i].t, w = e[x][i].w;
        if (t != p) {
            int c0 = cnt[1][0] - cnt[t][0], c1 = cnt[1][1] - cnt[t][1];
            ans = (ans + w * (cnt[t][0] * c1 + cnt[t][1] * c0)) % MOD;
            dfs2(t, x);
        }
    }
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", a + i);
        }
        for (int i = 1; i <= n; i++) {
            e[i].clear();
            par[i] = i;
            cnt[i][0] = cnt[i][1] = 0;
        }
        int x, y, pw = 1;
        for (int i = 1; i <= m; i++) {
            scanf("%lld%lld", &x, &y);
            pw = (pw << 1) % MOD;
            if (!same(x, y)) {
                merge(x, y);
                e[x].push_back(Edge(y, pw));
                e[y].push_back(Edge(x, pw));
            }
        }
        ans = 0;
        dfs1(1, 0), dfs2(1, 0);
        printf("%lld\n", ans);
    }
}

I - Divisibility

#include <iostream>
#include <stdio.h>
#include <string.h>
#define int long long

using namespace std;

int T, b, x;

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &b, &x);
        if (b % x == 1) {
            printf("T\n");
        } else {
            printf("F\n");
        }
    }
}

J - Expectation

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define MAX_M 10005
#define MOD 998244353
#define inv(x) (fpow(x, MOD - 2))
#define int long long

using namespace std;

int T, n, m;
int u[MAX_M];
int v[MAX_M];
int w[MAX_M];
int a[MAX_N][MAX_N];

void clear() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = 0;
        }
    }
}

void add(int x, int y) {
    a[x][x]++, a[y][y]++;
    a[x][y]--, a[y][x]--;
}

int fpow(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD, k >>= 1;
    }
    return ans;
}

int det(int a[][MAX_N], int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (!a[i][i]) {
            for (int j = i + 1; j <= n; j++) {
                if (a[j][i]) {
                    for (int k = 1; k <= n; k++) {
                        swap(a[i][k], a[j][k]);
                    }
                    ans = -ans;
                    break;
                }
            }
        }
        int t = inv(a[i][i]);
        for (int j = i + 1; j <= n; j++) {
            int f = a[j][i] * t % MOD;
            for (int k = i; k <= n; k++) {
                a[j][k] = (a[j][k] - a[i][k] * f % MOD) % MOD;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = ans * a[i][i] % MOD;
    }
    return (ans % MOD + MOD) % MOD;
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        clear();
        for (int i = 1; i <= m; i++) {
            scanf("%lld%lld%lld", u + i, v + i, w + i);
            if (u[i] != v[i]) {
                add(u[i], v[i]);
            }
        }
        int up = 0, dn = det(a, n - 1);
        for (int i = 0; i <= 30; i++) {
            clear();
            for (int j = 1; j <= m; j++) {
                if ((w[j] >> i) & 1) {
                    add(u[j], v[j]);
                }
            }
            up = (up + det(a, n - 1) * fpow(2, i) % MOD) % MOD;
        }
        printf("%lld\n", up * inv(dn) % MOD);
    }
}