FLAG: T2T3待加深理解 题面

T1

计算组合数，把所有乘除操作推到他们的质因子上，这样就没有除法操作了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n, Prim[100005], min_div[1000005], a[1000005], b[1000005], tot;
ll p, cc[1000005], ans = 1;

void read(int &x)
{
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
}

void euler(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!min_div[i])
            Prim[++tot] = i;
        for (int j = 1; j <= tot; ++j)
        {
            if (i * Prim[j] > n)
                break;
            min_div[i * Prim[j]] = Prim[j];
            if (i % Prim[j] == 0)
                break;
        }
    }
}

ll power(ll x, ll y)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ret;
}

int main()
{
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    cin >> n >> p;
    euler(1000000);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    for (int i = 1; i <= n; ++i)
        read(b[i]);
    for (int i = 1; i <= n; ++i)
    {
        cc[1]++;
        cc[b[i] + 1]--;
        cc[1]--;
        cc[b[i] - a[i] + 1]++;
        cc[1]--;
        cc[a[i] + 1]++;
    }
    for (int i = 1; i <= 1000000; ++i)
        cc[i] += cc[i - 1];
    for (int i = 1000000; i >= 2; --i)
    {
        if (min_div[i] != 0 && cc[i] != 0)
        {
            cc[min_div[i]] += cc[i];
            cc[i / min_div[i]] += cc[i];
            cc[i] = 0;
        }
    }
    for (int i = 2; i <= 1000000; ++i)
    {
        if (cc[i])
        {
            ans = ans * power(i, cc[i]) % p;
        }
    }
    cout << ans << endl;
    return 0;
}

T2

最后一条边肯定是T1和T2中同时存在的，把这条边两侧的点合并，然后继续重复操作即可
link

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

unordered_map<ll, int> mp;
unordered_set<int> st[1000010];
queue<pii> q;
int n, f[1000010];

int find(int x)
{
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}

ll getid(int x, int y)
{
    if (x < y)
        swap(x, y);
    return (ll)x * n + y;
}

int main()
{
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n * 2 - 2; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        st[x].insert(y);
        st[y].insert(x);
        mp[getid(x, y)]++;
        if (mp[getid(x, y)] == 2)
            q.push(pii(x, y));
    }
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    unordered_set<int>::iterator it;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        x = find(x);
        y = find(y);
        if (x == y)
            continue;
        st[x].erase(y);
        st[y].erase(x);
        if (st[x].size() < st[y].size())
            swap(x, y);
        for (it = st[y].begin(); it != st[y].end(); ++it)
        {
            int z = *it;
            mp[getid(y, z)] = 0;
            st[z].erase(y);
            st[z].insert(x);
            mp[getid(x, z)]++;
            st[x].insert(z);
            if (mp[getid(x, z)] == 2)
                q.push(pii(x, z));
        }
        f[y] = x;
        st[y].clear();
    }
    int s = 0;
    for (int i = 1; i <= n; ++i)
        s += (f[i] == i);
    if (s == 1)
        puts("YES");
    else
        puts("NO");
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-9/