T1

首先可以把阶乘的形式化为\(\prod_{i=a+1}^{b}i\)的形式

不难发现对于每一个数，当\(b-a\)固定时， a 和 b 也是固定的，且 b-a 最大只有20

于是就可以枚举 b-a，然后二分出 a，复杂度\(Tw\log n\)，w=20

T2

\(\frac{n}{k}\)为偶数时可以一条龙接上去

为奇数时沿用这个想法，考虑如何调整，发现要做的就是将前面的和制作出一个(排序后的)等差数列才能与最后一行抵消

然后就没了，注意一些无解和特判

T3

首先将操作和询问离线，维护一个以操作编号为下标的树状数组，然后在基岩上做扫描线

每个操作，在扫到的点是其左端点时，在编号的位置加上\(h_i\)，否则减去

回答询问在树状数组上二分出第一个前缀和大于 y 的位置，直接写是\(O(q\log^2n)\)

T4

由于删掉想(x,y)后 x 的排水量不变

可以将删一条边看做是 y 减少了一些排水量，x 的其他出边增加了一些排水量

更简便地，可以在 x 加上同时在 y 上减去以降低复杂度

代码

T1

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
struct ans_ {
    int a, b;
} vct[21];
int n;
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s;
}
int check(int x, int y) {
    int a = 1, b = 1;
    for (int i = 1; i <= y; ++i) {
        b = a;
        a *= (i + x - 1);
        if (a / (i + x - 1) != b || a > n)
            return 0;
    }
    return a;
}
void two(int x, int y) {
    int l = 1, r = sqrt(x);
    int ans = 1, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (!check(mid, y))
            r = mid - 1;
        else
            l = mid + 1, ans = mid;
    }
    if (ans == 1)
        return;
    if (check(ans, y) == x)
        vct[y] = { ans + y - 1, ans - 1 };
    return;
}
signed main() {
    FILE* x = freopen("factorial.in", "r", stdin);
    x = freopen("factorial.out", "w", stdout);
    int t = read();
    int st, num;
    while (t--) {
        for (int i = 1; i <= 20; ++i) vct[i] = { 0, 0 };
        num = 1;
        n = read();
        if (n == 1)
            printf("-1\n");
        else {
            vct[1] = { n, n - 1 };
            st = sqrt(n);
            if (st * (st + 1) == n && st != 1)
                vct[2] = { st + 1, st - 1 }, ++num;
            for (int i = 3; i <= 20; ++i) {
                two(n, i);
                if (vct[i].a)
                    ++num;
            }
            printf("%lld\n", num);
            for (int i = 20; i; --i)
                if (vct[i].a)
                    printf("%lld %lld\n", vct[i].a, vct[i].b);
        }
    }
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 11;
int n, k;
long long sum[N];
vector<int> vct[N];
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
int main() {
    FILE* x = freopen("subset.in", "r", stdin);
    x = freopen("subset.out", "w", stdout);
    int t = read();
    while (t--) {
        n = read();
        k = read();
        if (k == 1) {
            printf("Yes\n");
            for (int i = 1; i <= n; ++i) printf("%d ", i);
            printf("\n");
            continue;
        }
        if (k == n)
            printf("No\n");
        else if (!((n / k) & 1)) {
            printf("Yes\n");
            for (int i = 1; i <= n; ++i) vct[i].clear();
            for (int i = 1; i <= n / k; ++i) {
                if (i & 1)
                    for (int j = 1; j <= k; ++j) vct[j].push_back((i - 1) * k + j);
                else
                    for (int j = k; j; --j) vct[j].push_back(i * k - j + 1);
            }
            for (int j = 1; j <= k; ++j, printf("\n"))
                for (int i = 1; i <= n / k; ++i) printf("%d ", vct[j][i - 1]);
        } else {
            if (!(k & 1))
                printf("No\n");
            else {
                printf("Yes\n");
                for (int i = 1; i <= n; ++i) vct[i].clear();
                for (int i = 1; i <= n / k; ++i) {
                    if (i & 1)
                        for (int j = 1; j <= k; ++j) vct[j].push_back((i - 1) * k + j);
                    else
                        for (int j = k; j; --j) vct[j].push_back(i * k - j + 1);
                }
                for (int i = 1; i <= k / 2; ++i) vct[i][0] = k / 2 - i + 1;
                for (int i = k / 2 + 1; i <= k; ++i) vct[i][0] = k - i + k / 2 + 1;
                long long a = 0;
                for (int i = 1; i <= 3 * k; ++i) a += i;
                a /= k;
                for (int i = 1; i <= k; ++i) sum[i] = vct[i][0] + vct[i][1];
                for (int i = 1; i <= k; ++i) vct[i][2] = a - sum[i];
                for (int j = 1; j <= k; ++j, printf("\n"))
                    for (int i = 1; i <= n / k; ++i) printf("%d ", vct[j][i - 1]);
            }
        }
    }
    return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 11;
struct hi_ {
    int id;
    int hi;
};
vector<hi_> vctl[N];
vector<hi_> vctr[N];
vector<hi_> qry[N];
int n, q;
int tre[N];
int ans[N];
inline int lowbit(int x) { return x & -x; }
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s;
}
void insert(int x, int h) {
    while (x <= q) tre[x] += h, x += lowbit(x);
    return;
}
int query(int x) {
    int sum = 0;
    while (x) sum += tre[x], x -= lowbit(x);
    return sum;
}
void get_ans(int x, int h) {
    int l = 0, r = x - 1;
    int mid, as = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (query(mid) >= h)
            as = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    ans[x] = as ? as : -1;
    return;
}
signed main() {
    FILE* p = freopen("concrete.in", "r", stdin);
    p = freopen("concrete.out", "w", stdout);
    n = read(), q = read();
    for (int ty, l, r, h, x, y, i = 1; i <= q; ++i) {
        ty = read();
        if (ty == 1)
            l = read(), r = read(), h = read(), vctl[l].push_back({ i, h }), vctr[r].push_back({ i, h });
        else
            x = read(), y = read(), qry[x].push_back({ i, y });
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < vctl[i].size(); ++j) insert(vctl[i][j].id, vctl[i][j].hi);
        for (int j = 0; j < qry[i].size(); ++j) get_ans(qry[i][j].id, qry[i][j].hi);
        for (int j = 0; j < vctr[i].size(); ++j) insert(vctr[i][j].id, -vctr[i][j].hi);
    }
    for (int i = 1; i <= q; ++i)
        if (ans[i])
            printf("%lld\n", ans[i] == -1 ? 0 : ans[i]);
    return 0;
}

T4

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 11;
const int mod = 998244353;
struct qxxx {
    int v, next, w;
} cc[N];
int n, m, r, k;
int ans[N];
int inv[N];
int rd[N], cd[N], sum[N], w[N], tem[N];
int first[N], cnt;
queue<int> dui;
inline void md(int& x) {
    if (x >= mod)
        x -= mod;
    return;
}
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s;
}
int fm(int x, int y) {
    int as = 1;
    while (y) {
        if (y & 1)
            as = as * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return as;
}
void qxx(int u, int v, int w) {
    cc[++cnt] = { v, first[u], w };
    first[u] = cnt;
    return;
}
signed main() {
    FILE* p = freopen("water.in", "r", stdin);
    p = freopen("water.out", "w", stdout);
    n = read(), m = read();
    r = read(), k = read();
    int x, y, si = 0;
    for (int z, i = 1; i <= k; ++i) {
        x = read(), y = read(), z = read();
        md(si += z);
        qxx(x, y, z);
        ++rd[y], ++cd[x];
        ++tem[y];
    }
    si = fm(si, mod - 2);
    for (int i = 1; i <= n; ++i) inv[i] = fm(i, mod - 2);
    for (int i = 1; i <= m; ++i) dui.push(i), sum[i] = 1;
    int ny, nyh;
    while (dui.size()) {
        x = dui.front();
        dui.pop();
        ny = inv[cd[x]];
        nyh = inv[cd[x] - 1];
        for (int i = first[x]; i; i = cc[i].next) {
            y = cc[i].v;
            --tem[y];
            md(sum[y] += sum[x] * ny % mod);
            md(w[x] += cc[i].w * sum[x] % mod * cd[x] % mod * (nyh - ny + mod) % mod);
            md(w[y] += mod - cc[i].w * sum[x] % mod * nyh % mod);
            if (!tem[y])
                dui.push(y);
        }
    }
    for (int i = 1; i <= m; ++i) dui.push(i);
    while (dui.size()) {
        x = dui.front();
        dui.pop();
        for (int i = first[x]; i; i = cc[i].next) {
            y = cc[i].v;
            --rd[y];
            md(w[y] += w[x] * inv[cd[x]] % mod);
            if (!rd[y])
                dui.push(y);
        }
    }
    for (int i = n - r + 1; i <= n; ++i) md(sum[i] += w[i] * si % mod), printf("%lld ", sum[i]);
    return 0;
}