Sum Plus Product

题目大意：
在一个盒子里面有n个数，每次进行操作都会随机从盒子里面拿出两个数，将这两个数a，b变成一个数a+b+a*b，求最后得到的数的期望

input：
2
2
2 2
10
1 2 4 8 16 32 64 128 256 512

output：
8
579063023

解：
取出来的两个值结果会变成（a+1）*（b+1）-1再放回去，再将这个值+1乘以第三个数，会发现将所有值加一相乘最后减一就可以得到最终答案。

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define endl '\n'

const int N = 200005;
const ll mod = 998244353;

ll a[N];

void solve() {
    int n;
    cin >> n;
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 998244352) {
            cout << a[i] << endl;
            return;
        }
        ans *= a[i] + 1;
        ans %= mod;
    }
    if (ans == 0) {
        cout << 0 << endl;
        return;
    }
    cout << ans - 1 << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Shortest Path in GCD Graph

题目大意：
给定一张n个点的完全图，两个点之间的边的距离是他们的gcd，给定q次查询，每次查询给出两个点，问两个点之间最短路径和最短路径条数

input：
6 2
4 5
3 6

output：
1 1
2 2

解：
对每次的查询，最短路不是1就是2
因为每两个点之间都可以先走到1再走到另一个点，最短路是2.
如果这两个点之间的gcd等于1那么最短路就是1，路的条数也是1。
当路径长为2时我们还要找到有多少条这样的路，这就等价于gcd（a，x）=1，gcd（b，x）=1，（1<=x<=n），问你有多少个x满足条件
如何解决呢？考虑将这两个数质因数分解，问题就变成了在1-n里面有多少个数会被分解出来的质因数整除，用容斥定理求解

#include<bits/stdc++.h>

#define int long long
using namespace std;


int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a, b;
    vector<int> v;
    while (q--) {
        cin >> a >> b;
        v.clear();
        if (gcd(a, b) == 1) {
            cout << 1 << " " << 1 << endl;
            continue;
        } else {
            int k = a * b;
            for (int i = 2; i * i <= k; i++)
                if (k % i == 0) {
                    v.push_back(i);
                    while (k % i == 0)
                        k /= i;
                }
            if (k > 1) v.push_back(k);

            int sum = 0;
            for (int msk = 1; msk < (1 << v.size()); msk++) {
                int mult = 1, bits = 0;

                for (int i = 0; i < v.size(); ++i)
                    if (msk & (1 << i)) {
                        ++bits;
                        mult *= v[i];
                    }

                int cur = n / mult;

                if (bits % 2 == 1)
                    sum += cur;
                else
                    sum -= cur;
            }
            int res = n - sum;

            if (gcd(a, b) == 2) res++;
            cout << 2 << " " << res << endl;

        }
    }
}

Matryoshka Doll

题目大意：
给定n个玩偶，大小为𝑎1 ≤ 𝑎2 ≤ ... ≤ 𝑎𝑛，现在要将这些套娃分成𝑘组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求≥ 𝑟，求方案数。

input：
2
4 3 2
1 2 3 4
4 2 1
1 1 2 2

output：
3
2

解：
考虑dp[i][j]表示当前来到了i位置，之前的i-1个玩偶已经分成了j组
现在有两种选择，自己单成一组，或者是和之前的组合成组。
𝑑𝑝(𝑥, 𝑦) = 𝑑𝑝(𝑥 − 1, 𝑦 − 1) + 𝑑𝑝(𝑥 − 1, 𝑦) · max{0, 𝑦 − 𝑓 (𝑥)}
即单成一组+和之前成组
其中𝑓(𝑥)表示满足1 ≤ 𝑧 < 𝑥且𝑎𝑥 − 𝑟 < 𝑎𝑧 ≤ 𝑎𝑥的𝑧的个数，其实就是不能放的组的个数，用y减去这个数就是可以放的组数，下限为0

#include<bits/stdc++.h>

#define int long long
using namespace std;

int dp[5005][5005];
int a[5005];


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k, r;
        cin >> n >> k >> r;
        for (int i =0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {//当前来到了i位置
            int x = 0;
            for (int j = 1; j <= i - 1; j++) {
                if (a[i] - r < a[j]) {
                    x++;
                }
            }
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j - 1];
                dp[i][j] += dp[i - 1][j] * max(0ll, j - x) % 998244353;
                dp[i][j] %= 998244353;
            }
        }
        cout << dp[n][k] % 998244353 << endl;


    }
}