Exqule Forever

Nothing with me, but Forever.

国庆集训 Test 4

发布于 2020-10-07 | 分类于 特判 、 倒序 、 图计数 、 构造 、 差分 、 校内 | 12分钟 | 1904字数 | 浏览量：

国庆集训 Test 4

T1

考虑 a→b,c→d,e→fa \rightarrow b,c \rightarrow d,e \rightarrow f，如果 a×c×e<b×d×fa \times c \times e < b \times d \times f，那么也许可以，否则也许不行。

然而这样只能拿到 70 pts，之所以是也许，原因是你没有判 00 的存在（QAQ）。

#include <cstdio>
#include <cctype>
#include <iostream>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;char c = getchar();
    while(!isdigit(c)) {if (c == '-') f = - f;c = getchar();}
    while(isdigit(c)) x = x * 10 + (c ^ 48),c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7;
const lint INF = 1e18 + 1e9;

lint t, a, b, c, d, e, f;

void Solve() {
    a = readlint, b = readlint, c = readlint, d = readlint, e = readlint, f = readlint;
    if (b * d * f) {
        if (a * c * e) puts(a * c * e < b * d * f ? "MEI" : "FON");
        else puts("MEI");
    }
    else {
        if (!d || !c) puts(!d ? "FON" : "MEI");
        else if (!b || !a) puts(!b ? "FON" : "MEI");
        else puts("FON");
    }
    return ;
}

int main(void) {
    
    scanf("%lld", &t);
    while(t --) Solve();
    
    return 0;
}

T2

我们发现对于所有的操作 2 仅会进行其之前的操作，那么考虑把所有操作倒序处理。

每次操作 2 都把所有在此之前的操作次数 + 1，那么每当执行到一次操作 1 时，区间修改一次完成。

由于我们只关心所有操作结束后的序列，那么很容易进行差分。也不知道考场上什么心态怒码线段树

#include <cstdio>
#include <cctype>
#include <iostream>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = - f;c = getchar();}
    while (isdigit(c)) x = x * 10 + (c ^ 48),c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e5 + 1e1, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

struct Node {
    int l, r;
    lint w, lazy;
} ;

int op[MAXN], L[MAXN], R[MAXN], n, m;

void Abs(lint &x) {
    while (x >= Mod) x -= Mod;
    return ;
}

struct SegmentTree {
    Node tree[MAXN << 2];
    
    void Pushup(int x) {
        Abs(tree[x].w = tree[x << 1].w + tree[x << 1 | 1].w);
        return ;
    }
    
    void Build(int l, int r, int x) {
        tree[x].l = l, tree[x].r = r;
        if (l == r) tree[x].w = tree[x].lazy = 0;
        else {
            int mid = l + r >> 1;
            Build(l, mid, x << 1), Build(mid + 1, r, x << 1 | 1);
        }
        return ;
    }
    
    void Pushdown(int x) {
        if (tree[x].lazy) {
            int l = tree[x].l, r = tree[x].r, mid = l + r >> 1;
            Abs(tree[x << 1].lazy += tree[x].lazy);
            Abs(tree[x << 1 | 1].lazy += tree[x].lazy);
            Abs(tree[x << 1].w += (((mid - l + 1) * tree[x].lazy) % Mod));
            Abs(tree[x << 1 | 1].w += (((r - mid) * tree[x].lazy) % Mod));
        }
        tree[x].lazy = 0;
        return ;
    }
    
    void Update(int ql, int qr, lint k, int x) {
        int l = tree[x].l, r = tree[x].r;
        if (qr < l || r < ql) return ;
        if (ql <= l && r <= qr) {
            Abs(tree[x].w += (((r - l + 1) * k) % Mod));
            Abs(tree[x].lazy += k);
        }
        else Pushdown(x), Update(ql, qr, k, x << 1), Update(ql, qr, k, x << 1 | 1), Pushup(x);
        return ;
    }
    
    lint Query(int ql, int qr, int x) {
        int l = tree[x].l, r = tree[x].r;
        lint res = 0;
        if (qr < l || r < ql) ;
        else {
            if (ql <= l && r <= qr) res = tree[x].w;
            else Pushdown(x), res = (Query(ql, qr, x << 1) + Query(ql, qr, x << 1 | 1)) % Mod;
        }
        return res;
    }
} st1, st2;

int main(void) {
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++) op[i] = readint, L[i] = readint, R[i] = readint;
    st1.Build(1, m, 1), st2.Build(1, n, 1);
    for (int i = m; i; i --) {
        lint k = st1.Query(i, i, 1) + 1;
        if (op[i] ^ 1) st1.Update(L[i], R[i], k, 1);
        else st2.Update(L[i], R[i], k, 1);
    }
    for (int i = 1; i <= n; i ++) printf("%lld ", st2.Query(i, i, 1));
    puts("");
    
    return 0;
}

T3

乍一看发现是图计数，当即心凉。

How Difficult The Counting Problem Is! JOJO! I Am Sorry To Be Born!

考场上写了个爆搜和 k=1k=1 的情况。

k=1k = 1 的情况即考虑每条边对于答案的贡献为 2n−22^{n - 2}，总答案为 m×2n−2m \times 2^{n-2}。

但其实我们对于 k=2k = 2 的贡献也可以如此考虑，即给 ∣E∣2|E|^{2} 赋予一个组合意义。

考虑一个连通块内的边对数量其实就是他的组合意义，那么分类讨论计算贡献即可。

然而分类讨论巨多，狂码 3h+ 后终于过了[擦汗]。

#include <cstdio>
#include <cctype>
#include <iostream>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = - f;c = getchar();}
    while (isdigit(c)) x = x * 10 + (c ^ 48),c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, Mod = 1e9 + 7;
const lint INF = 1e18 + 1e9;

int n, m, k;

lint Qpow(lint A, int B) {
    lint res = 1;
    while (B > 0) {
        if (B & 1) (res *= A) %= Mod;
        (A *= A) %= Mod, B >>= 1;
    }
    return res;
}

namespace Subtask1 {
const int MAXN = 16;

bool vis[MAXN];
int e[MAXN][MAXN];
lint Ans = 0;

void Dfs(int dep, lint f) {
    if (dep == n) {
        (Ans += Qpow(f, k)) %= Mod;
        return ;
    }
    Dfs(dep + 1, f);
    for (int i = 1; i <= n; i ++) {
        if (dep + 1 == i) continue ;
        if (vis[i] && e[dep + 1][i]) ++ f;
    }
    vis[dep + 1] = true;
    Dfs(dep + 1, f);
    vis[dep + 1] = false;
    return ;
}

void Solve() {
    for (int i = 1; i <= m; i ++) {
        int u = readint, v = readint;
        ++ e[u][v], ++ e[v][u];
    }
    Dfs(0, 0);
    printf("%lld\n", Ans);
    return ;
}

}

namespace Subtask2 {
lint Ans = 0;

void Solve() {
    Ans = m * Qpow(2, n - 2);
    printf("%lld\n", Ans % Mod);
    return ;
}

}

namespace Subtask3 {
const int MAXN = 1e5 + 1e1;

struct Edge {
    int u, v;
} e[MAXN];
lint deg[MAXN], Ans = 0;

void Solve() {
    Ans = (m * Qpow(2, n - 2)) % Mod;
    for (int i = 1; i <= m; i ++) {
        e[i].u = readint, e[i].v = readint;
        ++ deg[e[i].u], ++ deg[e[i].v];
    }
    for (int i = 1; i <= m; i ++) {
        int u = e[i].u, v = e[i].v;
        (Ans += ((deg[u] - 1) * Qpow(2, n - 3)) % Mod) %= Mod;
        (Ans += ((deg[v] - 1) * Qpow(2, n - 3)) % Mod) %= Mod;
        (Ans += ((m - deg[u] - deg[v] + 1) * Qpow(2, n - 4)) % Mod) %= Mod;
    }
    printf("%lld\n", Ans);
    return ;
}

}

namespace Subtask4 {
const int MAXN = 1e5 + 1e1;

struct Edge {
    int u, v;
} e[MAXN];
struct EdgeTo {
    int nxt, to;
} et[MAXN << 1];
bool book[MAXN];
int head[MAXN], tot = 0;
lint deg[MAXN], Ans = 0, cnt = 0, tmp = 0, num = 0, thr = 0;

void Addedge(int u, int v) {
    et[++ tot] = (EdgeTo){head[u], v};
    head[u] = tot;
    return ;
}

void Solve() {
    for (int i = 1; i <= m; i ++) {
        e[i].u = readint, e[i].v = readint;
        ++ deg[e[i].u], ++ deg[e[i].v];
    }
    for (int i = 1; i <= m; i ++) {
        if (deg[e[i].u] > deg[e[i].v]) Addedge(e[i].u, e[i].v);
        if (deg[e[i].u] < deg[e[i].v]) Addedge(e[i].v, e[i].u);
        if (deg[e[i].u] == deg[e[i].v]) {
            if (e[i].u > e[i].v) swap(e[i].u, e[i].v);
            Addedge(e[i].u, e[i].v);
        }
    }
    for (int i = 1; i <= m; i ++) {
        int u = e[i].u, v = e[i].v;
        (Ans += ((deg[u] - 1) * Qpow(2, n - 3)) % Mod) %= Mod;
        (Ans += ((deg[v] - 1) * Qpow(2, n - 3)) % Mod) %= Mod;
        (Ans += ((m - deg[u] - deg[v] + 1) * Qpow(2, n - 4)) % Mod) %= Mod;
    }
    (Ans = (Ans * 3) % Mod + (m * Qpow(2, n - 2)) % Mod) %= Mod;
    for (int i = 1; i <= n; i ++) {
        for (int j = head[i]; j; j = et[j].nxt) book[et[j].to] = true;
        for (int j = head[i]; j; j = et[j].nxt) {
            for (int k = head[et[j].to]; k; k = et[k].nxt) {
                if (book[et[k].to] && et[k].to != i) ++ thr;
            }
        }
        memset(book, false, sizeof(book));
    }
    for (int i = 1; i <= m; i ++) (tmp += (deg[e[i].u] - 1) * (deg[e[i].v] - 1) % Mod) %= Mod;
    for (int i = 1; i <= n; i ++) if(deg[i] >= 3) (num += (deg[i] - 2) * (deg[i] - 1) % Mod * deg[i] % Mod * Qpow(6, Mod - 2) % Mod) %= Mod;
    for (int i = 1; i <= n; i ++) (cnt += (deg[i] * (deg[i] - 1) % Mod * Qpow(2, Mod - 2)) % Mod) %= Mod;
    tmp = (((tmp + num) % Mod) + Mod - (3 * thr % Mod)) % Mod, (Ans += Qpow(2, n - 3) * 6 % Mod * thr % Mod + Qpow(2, n - 4) * 6 % Mod * tmp % Mod) %= Mod;
    cnt = (Mod + ((m - 2) * cnt % Mod - num + Mod) - (((tmp * 2 % Mod) + (thr * 3 % Mod)) % Mod)) % Mod;
    (Ans += ((cnt * 6 % Mod) * Qpow(2, n - 5)) % Mod) %= Mod, Ans += Qpow(2, n - 6) * (((Mod - ((thr + cnt + tmp) % Mod * 6 % Mod)) + (1ll * m * (m - 1) % Mod * (m - 2) % Mod)) % Mod) % Mod;
    printf("%lld\n", Ans % Mod);
    return ;
}

}

int main(void) {
    
    scanf("%d%d%d", &n, &m, &k);
    if (n <= 4) Subtask1 :: Solve();
    else if (k == 1) Subtask2 :: Solve();
    else if (k == 2) Subtask3 :: Solve();
    else if (k == 3) Subtask4 :: Solve();
    
    return 0;
}
# 特判 # 倒序 # 图计数 # 构造 # 差分 # 校内
李超线段树 上一篇
二项式反演 下一篇
0%