E - Range Sums

题意：

现在有长度为\(N\)的序列，\(a_1....a_n\),给Q条信息，每条消息，会告诉你\(a_l+.....a_r\)的和，现在问，给定\(Q\)条信息后，能否
确定\(a_1+a_2+......a_n\)的和

思路：

每次令\(sum_i\)为\(a\)数组的前缀和
那么给定\(a_l+.....a_r\),相当于已知\(sum_{r}-sum_{l-1}\)的值
那么要确定\(a_1+a_2+......a_n\)的和，就是看能否知道\(sum_N-sum_0\)的值，也就是看\(0\)和\(N\)是否在一个集合中，每给定一个信息，就相当于\(r和(l-1)\)连一条边

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int mod = 998244353;
int fa[N];
int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void Union(int a, int b) {
    a = find(a), b = find(b);
    if (a != b) {
        fa[a] = b;
    }
}
signed main() {
    int n, T;
    cin >> n >> T;
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= T; i++) {
        int x, y;
        cin >> x >> y;
        Union(x-1,y);
    }

    if (find(0) == find(n)) {
        puts("Yes");
    } else {
        puts("No");
    }
}

F - Two Exams

题意：

现在有\(N\)个人，每个人都有\(2\)科成绩名次，现在需要选出\(K\)个参加比赛，选人时不能出现的情况为，假设选了\(x\),没选\(y\)，但是\(y\)的两科名次都比\(x\)高，这种选法是不合法的，现在问有多少种合法的选法

思路：

先将所有人按照第一科成绩排序，从前往后遍历时，前面选的人的科目排名比后面的高
定义\(f(i,j,k)\)为考虑了前\(i\)个人，选了\(j\)个人，没选的人的最高排名为\(k\)的情况数
假设现在不选\(i\)号人物
那么\(f(i,j,min(e[i].b,k))=f(i-1,j,k))\)
如果\(e[i].b<k\)
那么 就可以考虑选\(i\)号人物
\(f(i,j+1,k)+=f(i-1,j,k)\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 333;
int f[N][N][N];
struct node {
    int a, b;
} e[N];
int dp[N][N][N];
int n, k;
bool cmp(node a,node b) {
    return a.a<b.a;
}
signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> e[i].a;
    }
    for (int i = 1; i <= n; i++) {
        cin >> e[i].b;
    }
    sort(e + 1, e + n + 1,cmp);
    f[0][0][n + 1] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int x = 1; x <= n + 1; x++) {
                f[i][j][min(e[i].b, x)] += f[i - 1][j][x] % mod;
                f[i][j][min(e[i].b, x)] %= mod;
                if (e[i].b < x) {
                    f[i][j + 1][x] += f[i - 1][j][x] % mod;
                    f[i][j + 1][x] %= mod;
                }
            }
        }
    }
    
    int res = 0;
    for (int i = 1; i <= n + 1; i++) {
        res += f[n][k][i] % mod;
        res %= mod;
    }
    cout << res << endl;
}

G - Cubic?

题意：

现在给定长度为\(N\)的序列，\(A_1....A_N\),\(Q\)次询问，每次询问\(A_l×A_{l+1}....A_r\)这个数是否是立方数

思路：

由于是相乘，质因数分解后，质因数对应的指数就是相加，问是否立方数，就看结果质因数分解后，对应的指数都是\(3\)的倍数，此时就是可以对每个数的质因数进行哈希，由于是看指数是否是\(3\)的倍数，那么指数就可以对\(3\)取模，对每个数的质因子进行哈希，再对哈希值求一边前缀和，最终就看\(sum_r-sum_{l-1}\)是否为\(0\)即可，为\(0\)代表着这段区间的质因子的指数和都满足是\(3\)的倍数，说明是立方数

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int P = 131;
const int mod = 998244353;
int p[N], Hash[N];
int cnt[N];
int n, T;
int all;
void init() {
    p[0] = 1;
    for (int i = 1; i < N; i++) {
        p[i] = p[i - 1] * 131 % mod;
    }
}
void cal(int x, int y) {
    all -= p[x] * cnt[x] % mod;
    if (all < 0) all += mod;
    cnt[x] += y;
    cnt[x] %= 3;
    all += p[x] * cnt[x] % mod;
    all %= mod;
}
signed main() {
    init();
    scanf("%lld%lld", &n, &T);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%lld", &x);
        for (int j = 2; j <= x / j; j++) {
            if (x % j == 0) {
                int cnt = 0;
                while (x % j == 0) {
                    cnt++;
                    x /= j;
                }
                cal(j, cnt);
            }
        }
        if (x != 1) {
            cal(x, 1);
        }
        Hash[i] = all;
    }
    for (int i = 1; i <= T; i++) {
        int l, r;
        scanf("%lld%lld", &l, &r);
        if (Hash[r] - Hash[l - 1] == 0) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}