Namomo Test Round 1 – Hat

题目链接

https://namomo.top:8081/problem/1005

tag

线段树

solution

对于看不见的操作,有两种情况:
​ 1) 如果兔子在第\(i\)个帽子下面，操作完后帽子仍在第\(i\)个帽子下，我们可能选择除第\(i\)个帽子以外的任意两个帽子进行交换，概率为\(\frac{C_{n-1}^{2}}{C_{n}^{2}}\)
2)如果兔子不在第\(i\)给帽子下面, 则需要操作后兔子在第\(i\)个帽子下，此时我们只有一种操作可能，即将兔子所在的帽子和第\(i\)个帽子交换，概率为 \(\frac{1}{C_n^2}\)
所以有\(p[i] = \frac{p[i] * C_{n-1}^{2}}{C_{n}^{2}} + \frac{(1 - p[i])}{C_n^2}\)

对于看得见的操作，直接\(swap(p[x], p[y])\)

发现维护p[i]的值需要的进行操作有单点修改，单点查询，区间加法，区间乘法，建一个线段树就可以解决了,另外分数取模需要用到逆元

时间复杂度为\(O(n + k + mlogn)\)

code

//created by pyoxiao on 2020/07/06
#include<bits/stdc++.h>
#define LL long long
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define CL(a, b) memset(a, b, sizeof(a))
using namespace std;
const LL mod = 998244353, p = mod;
LL fpow(LL a, LL b, LL p = mod){LL ans = 1; a %= p; while(b) {if(b & 1) ans = ans * a % p; b >>= 1; a = a * a % p;} return ans;}
LL gcd(LL a, LL b){return b == 0 ? a : gcd(b, a % b);}
LL inv(LL x) {return fpow(x, mod - 2);}
const int N = 2e5 + 7;
LL n, m, k, op[N], x[N], y[N];
struct seg{
    int l, r;
    LL sum, add, mul;
}tr[N << 2];
void push_up(int p) {
    tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % mod;
    tr[p].add = 0; tr[p].mul = 1;
}
void build(int l, int r, int p) {
    tr[p].l = l; tr[p].r = r; tr[p].add = 0; tr[p].mul = 1; tr[p].sum = 0;
    if(l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, p << 1);
    build(mid + 1, r, p << 1 | 1);
    push_up(p);
}
void change(int p, LL add, LL mul) {
    tr[p].mul = tr[p].mul * mul % mod;
    tr[p].add = (tr[p].add * mul % mod + add) % mod;
    tr[p].sum = ((tr[p].sum * mul % mod + add * (tr[p].r - tr[p].l + 1) % mod) % mod + mod) % mod;
}
void push_down(int p) {
    change(p << 1, tr[p].add, tr[p].mul);
    change(p << 1 | 1, tr[p].add, tr[p].mul);
    tr[p].add = 0; tr[p].mul = 1;
}
void update(int p, int l , int r, LL add, LL mul) {
    if(l <= tr[p].l && tr[p].r <= r) {
        change(p, add, mul);
        return;
    }
    push_down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if(l <= mid) update(p << 1, l, r, add, mul);
    if(r > mid) update(p << 1 | 1, l, r, add, mul);
    push_up(p);
}
void update2(int p, int pos, LL val) {
    if(tr[p].l == pos && tr[p].r == pos) {
        tr[p].sum = val; tr[p].add = 0; tr[p].mul = 1;
        return;
    }
    push_down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if(pos <= mid) update2(p << 1, pos, val);
    else update2(p << 1 | 1, pos, val);
    push_up(p);
}
LL query(int p, int l, int r) {
    if(l <= tr[p].l && tr[p].r <= r) return tr[p].sum;
    push_down(p);
    LL ans = 0;
    int mid = tr[p].l + tr[p].r >> 1;
    if(l <= mid) ans += query(p << 1, l, r), ans %= mod;
    if(r > mid) ans += query(p << 1 | 1, l, r), ans %= mod;
    return ans % mod;
}
void solve() {
    scanf("%lld %lld %lld", &n, &m, &k);
    build(1, n, 1);
    update2(1, 1, 1);
    for(int i = 1; i <= m; i ++) op[i] = 0;
    for(int i = 1; i <= k; i ++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        op[a] = 1; x[a] = b; y[a] = c;
    }
    int pos = 1;
    LL add = (2LL *  inv(n * (n - 1)) % mod + mod) % mod, mul = (((n - 2) * inv(n) % mod - 2LL * inv(n * (n - 1)) % mod + mod) % mod + mod) % mod;
    for(int i = 1; i <= m; i ++) {
        if(op[i]) {
            LL tmp1 = query(1, x[i], x[i]), tmp2 = query(1, y[i], y[i]);
            update2(1, x[i], tmp2);
            update2(1, y[i], tmp1);
        } else {
            update(1, 1, n, add, mul);
        }
    }
    for(int i = 1; i <= n; i ++) printf("%lld%c", (query(1, i, i) % mod + mod) % mod, i == n ? '\n' : ' ');
}
int main() {
    int T = 1;
    scanf("%d", &T);
    while(T --) 
        solve();
    return 0;
}