2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

A.^&^

签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll A, B, C;

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%lld%lld", &A, &B);
        C = 0;
        for (int i = 32; i >= 0; --i) {
            if ((A >> i) % 2 && (B >> i) % 2)
                C |= (1ll << i);
        }
        if (C == 0) {
            for (int i = 0; i <= 32; ++i) {
                if (((A >> i) % 2) + ((B >> i) % 2) == 1) {
                    C |= (1ll << i);
                    break;
                }
            }
        }
        printf("%lld\n", C);
    }
    return 0;
}

B. array

权值线段树线段树维护每个数出现的下标，树上二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

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

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, q, m, a[N], b[N];

struct SEG {
    int t[N << 2];
    void build(int id, int l, int r) {
        if (l == r) {
            t[id] = b[l]; 
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void update(int id, int l, int r, int pos) { 
        if (l == r) {
            t[id] = INF;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos);
        else update(id << 1 | 1, mid + 1, r, pos);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    int ask(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return t[id];
        int mid = (l + r) >> 1;
        int res = 0;
        if (ql <= mid) res = max(res, ask(id << 1, l, mid, ql, qr));
        if (qr > mid) res = max(res, ask(id << 1 | 1, mid + 1, r, ql, qr));
        return res;
    }
    int query(int id, int l, int r, int k, int R) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (mid < k || ask(id << 1, l, mid, k, mid) <= R) return query(id << 1 | 1, mid + 1, r, k, R);
        if (t[id << 1] <= R) return query(id << 1 | 1, mid + 1, r, k, R);
        else return query(id << 1, l, mid, k, R);
    }
}seg;

int main() {
    int _T; cin >> _T; 
    while (_T--) {
        scanf("%d%d", &n, &q); m = n + 1;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[a[i]] = i; 
        b[m] = INF;
        seg.build(1, 1, m);
        int lstans = 0; 
        for (int _q = 1, op, x, k; _q <= q; ++_q) {
            scanf("%d%d", &op, &x);
            x ^= lstans;
            if (op == 1) {
                seg.update(1, 1, m, a[x]);
            } else {
                scanf("%d", &k);
                k ^= lstans;
                printf("%d\n", lstans = seg.query(1, 1, m, k, x));
            }
        }
    }
    return 0;
}

C. K-th occurrence

队友太强了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

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

const int N = 1e5 + 10;
const int M = 23;
int n, q;
char s[N];
struct DA {
    int t1[N], t2[N], c[N];
    int sa[N];
    int Rank[N];
    int height[N];
    int str[N];
    int n, m;
    void init(char *s, int m, int n) {
        this->m = m;
        this->n = n;
        for (int i = 0; i < n; ++i) str[i] = s[i];
        str[n] = 0;
    }
    bool cmp(int *r, int a, int b, int l) {
        return r[a] == r[b] && r[a + l] == r[b + l];
    }
    void work() {
        ++n;
        int i, j, p, *x = t1, *y = t2;
        for (i = 0; i < m; ++i) c[i] = 0;
        for (i = 0; i < n; ++i) c[x[i] = str[i]]++;
        for (i = 1; i < m; ++i) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
        for (j = 1; j <= n; j <<= 1) {
            p = 0;
            //直接利用sa数组排序第二关键字
            //后面的j个数第二关键字为空的最小
            for (i = n - j; i < n; ++i) {
                y[p++] = i;
            }
            for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
            //这样数组y保存的就是按照第二关键字排序的结果
            //基数排序第一关键字
            for (i = 0; i < m; ++i) c[i] = 0;
            for (i = 0; i < n; ++i) c[x[y[i]]]++;
            for (i = 1; i < m; ++i) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
            //根据sa和x数组计算新的x数组
            swap(x, y);
            p = 1; x[sa[0]] = 0;
            for (i = 1; i < n; ++i) {
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
            }
            if (p >= n) break;
            //下次基数排序的最大值
            m = p;
        }
        int k = 0;
        --n;
        for (i = 0; i <= n; ++i) Rank[sa[i]] = i;
        //build height
        for (i = 0; i < n; ++i) {
            if (k) --k;
            j = sa[Rank[i] - 1];
            while (str[i + k] == str[j + k]) ++k;
            height[Rank[i]] = k; 
        }
    }
    struct RMQ {
        int Min[N][M]; 
        int mm[N];
        void init(int n, int *b) {
            mm[0] = -1;
            for (int i = 1; i <= n; ++i) {
                mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
                Min[i][0] = b[i];
            }
            for (int j = 1; j <= mm[n]; ++j) {
                for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                    Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
        int queryMin(int x, int y) {
            int k = mm[y - x + 1];
            return min(Min[x][k], Min[y - (1 << k) + 1][k]);  
        }
    }rmq;
    void initrmq() {
        rmq.init(n, height);
    }
    int lcp(int x, int y) {
        if (x == y) return 1e9;
        if (x > y) swap(x, y);
        ++x;
        return rmq.queryMin(x, y);   
    }
}da;

int getl(int x, int len) {
    int l = 1, r = x, res = x;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (da.lcp(x, mid) >= len) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int getr(int x, int len) {
    int l = x, r = n, res = x;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (da.lcp(x, mid) >= len) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

struct SEG {
    struct node {
        int sum, ls, rs;
        node() {
            ls = rs = sum = 0;
        } 
    }t[N * 50];
    int rt[N], cnt;
    void init() { 
        cnt = 0; 
        memset(rt, 0, sizeof rt);
    }
    void build(int &id, int l, int r) {
        id = ++cnt;
        t[id] = node();
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(t[id].ls, l, mid);
        build(t[id].rs, mid + 1, r);  
    }
    void up(int id) {
        int ls = t[id].ls, rs = t[id].rs;
        t[id].sum = 0;
        if (ls) t[id].sum += t[ls].sum;
        if (rs) t[id].sum += t[rs].sum; 
    }
    void update(int &now, int pre, int l, int r, int pos) {
        now = ++cnt;
        t[now] = t[pre];  
        if (l == r) {
            ++t[now].sum; 
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(t[now].ls, t[pre].ls, l, mid, pos);
        else update(t[now].rs, t[pre].rs, mid + 1, r, pos);
        up(now);
    }
    int query(int tl, int tr, int l, int r, int k) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int lsum = t[t[tr].ls].sum - t[t[tl].ls].sum;    
        if (lsum >= k) {
            return query(t[tl].ls, t[tr].ls, l, mid, k);
        } else {
            return query(t[tl].rs, t[tr].rs, mid + 1, r, k - lsum); 
        }
    }
}seg;

int main() {
    int _T; scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d", &n, &q);
        scanf("%s", s);
        da.init(s, 220, n);
        da.work(); da.initrmq();
        seg.init(); seg.build(seg.rt[0], 1, n);  
        for (int i = 1; i <= n; ++i)
            seg.update(seg.rt[i], seg.rt[i - 1], 1, n, da.sa[i] + 1);
        for (int i = 1, x, l, r, k, len; i <= q; ++i) {
            scanf("%d%d%d", &l, &r, &k);
            len = r - l + 1; 
            x = da.Rank[l - 1];  
            int L = getl(x, len);
            int R = getr(x, len);
            if (R - L + 1 < k) puts("-1");
            else printf("%d\n", seg.query(seg.rt[L - 1], seg.rt[R], 1, n, k));   
        }
    }
    return 0;
}

D. path

维护一个大小为MaxKMaxK的multisetmultiset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

struct Edge {
    int to, w;

    Edge() {}
    
    Edge(int to, int w) : to(to), w(w) {}
    
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

struct node {
    int now;
    ll w;

    node() {}
    
    node(int now, ll w) : now(now), w(w) {}
    
    bool operator<(const node &other) const {
        if (w == other.w) {
            return now < other.w;
        } else {
            return w < other.w;
        }
    }
};

int n, m, q, MaxK;
vector<vector<Edge>> G;
int Q[N];
ll res[N];
multiset<node> s;

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &q);
        G.clear();
        G.resize(n + 1);
        s.clear();
        for (int i = 1, u, v, w; i <= m; ++i) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(Edge(v, w));
        }
        MaxK = 0;
        for (int i = 1; i <= q; ++i) {
            scanf("%d", Q + i);
            MaxK = max(MaxK, Q[i]);
        }
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
            for (auto it : G[i]) {
                if (s.empty()) {
                    s.insert(node(it.to, it.w));
                    continue;
                }
                if (s.size() >= MaxK + 1) {
                    auto item = s.end();
                    item--;
                    if (it.w >= (*item).w) {
                        break;
                    } else {
                        s.erase(item);
                        s.insert(node(it.to, it.w));
                    }
                } else {
                    s.insert(node(it.to, it.w));
                }
            }
        }
        for (int i = 1; i <= MaxK; ++i) {
            res[i] = (*s.begin()).w;
            if (i == MaxK) break;
            int u = (*s.begin()).now;
            ll w = (*s.begin()).w;
            s.erase(s.begin());
            for (auto it : G[u]) {
                node now = node(it.to, w + it.w);
                if (s.empty()) {
                    s.insert(now);
                    continue;
                }
                if (s.size() >= MaxK - i + 1) {
                    auto item = s.end();
                    item--;
                    if (now.w >= (*item).w) {
                        break;
                    } else {
                        s.erase(item);
                        s.insert(now);
                    }
                } else {
                    s.insert(now);
                }
            }
        }
        for (int i = 1; i <= q; ++i) {
            printf("%lld\n", res[Q[i]]);
        }
    }
    return 0;
}

E. huntian oy

队友太强了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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

#define ll long long
const int N = 2e6 + 10;
const int M = 1e5 + 10;
const ll mod = 1e9 + 7;
int pri[N], check[N], phi[N], tot;
ll f[N], F[N], inv2, inv6, n, a, b; 
void init() {
    memset(check, 0, sizeof check);
    tot = 0;
    phi[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!check[i]) {
            pri[++tot] = i;
            phi[i] = i - 1;
        } 
        for (int j = 1; j <= tot; ++j) {
            if (1ll * i * pri[j] >= N) break;
            check[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } else {
                phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
            }
        }
    }
    f[1] = 0;
    for (int i = 1; i < N; ++i) {
        f[i] = f[i - 1];
        f[i] += 1ll * i * phi[i] % mod;
        f[i] %= mod;
    }
}

ll qpow(ll base, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}

ll sum_2(ll n) {
    return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
}

ll sum(ll n) {
    return n * (n + 1) % mod * inv2 % mod;
}

map <int, int> mp;
bool vis[M]; 
ll S(ll x) {
    if (x < N) return f[x];
    if (mp.find(x) != mp.end()) return mp[x];
    ll res = sum_2(x);
    for (int i, j = 1; j < x; ) {
        i = j + 1;
        j = x / (x / i);
        res += mod - (sum(j) - sum(i - 1) + mod) % mod * S(x / i) % mod;
        res = res % mod;
    }
    return mp[x] = res;
}

int main() {
    init();
    inv2 = qpow(2, mod - 2); inv6 = qpow(6, mod - 2);
    mp.clear();
    memset(vis, 0, sizeof vis);
    int _T; scanf("%d", &_T);
    while (_T--) {
        scanf("%lld%lld%lld", &n, &a, &b);
        ll res = S(n);
        res = (res + mod - 1) % mod;
        res = res * inv2 % mod;
        printf("%lld\n", res);
    }
    return 0;
}

F. Shuffle Card

签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

int n, m;
int a[N], b[N], vis[N], res[N];

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    while (~scanf("%d %d", &n, &m)) {
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d", b + i);
        }
        int cnt = 0;
        for (int i = m; i >= 1; --i) {
            if (vis[b[i]]) {
                continue;
            }
            vis[b[i]] = 1;
            res[++cnt] = b[i];
        }
        for (int i = 1; i <= n; ++i) {
            if (!vis[a[i]]) {
                res[++cnt] = a[i];
            }
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", res[i]);
        }
    }
    return 0;
}

G. Windows Of CCPC

签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

const int N = 1100;
int n, k;
char s[N][N]; 

void gao(int x, int y, int k) {
    if (k == 1) {
        s[x][y] = 'C';
        s[x][y + 1] = 'C';
        s[x + 1][y] = 'P';
        s[x + 1][y + 1] = 'C';
        return;
    } else {
        int n = 1 << (k - 1);
        gao(x, y, k - 1);
        gao(x, y + n, k - 1);
        gao(x + n, y, k - 1);
        gao(x + n, y + n, k - 1);
        for (int i = x + n; i < x + 2 * n; ++i) {
            for (int j = y; j < y + n; ++j) {
                if (s[i][j] == 'C') s[i][j] = 'P';
                else s[i][j] = 'C';
            }
        }
    }
}

int main() {
    int _T; scanf("%d", &_T);
    while (_T--) {
        int k; scanf("%d", &k);
        n = 1 << k;
        gao(1, 1, k);    
        for (int i = 1; i <= n; ++i) {
            s[i][n + 1] = 0;
            printf("%s\n", s[i] + 1);
        }
    }
    return 0;
}

H. Fishing Master

假设都在炖鱼的时候捕鱼，那么再补一条鱼的时间为k−a[i]%kk-a[i]\%k，根据这个排序，保证正好nn条鱼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

int n, k;
ll a[N];


int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &k);
        ll cnt = 1, res = k;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", a + i);
            res += a[i];
            cnt += a[i] / k;
            a[i] %= k;
        }
        cnt -= n;
        cnt = -cnt;
        sort(a + 1, a + 1 + n);
        for (int i = n; i >= 1 && cnt > 0; --i, --cnt) {
            res += k - a[i];
        }
        printf("%lld\n", res);
    }
    return 0;
}

I. Kaguya

题意：一个二分图，左边有有nn个点，右边有mm个点，两点连接概率为12\frac{1}{2}，其期望

思路：dp[i][j][k][l]dp[i][j][k][l]表示BFSBFS到第ii层，左边用了jj个点，右边用了kk个点，当前层有ll个点，那么如果当前层为左边，下一层为右边，dp[i+1][j][k+o][o]=dp[i][j][k][l]∗P,P=(m−ko)⋅(2l−1)o2l⋅(m−k)dp[i+1][j][k+o][o]=dp[i][j][k][l]*P, P=\tbinom{m-k}{o}\cdot \frac{(2^l-1)^o}{2^{l\cdot (m-k)}}

枚举转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 31;

ll p;

ll qpow(ll x, ll n) {
    ll res = 1;;
    while (n) {
        if (n & 1)res = res * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return res;
}

int n, m;
int C[N][N];
int pw2[N * N], pw3[N][N], INV[N * N];
int f[N << 1][N][N][N];

void pre() {
    C[0][0] = 1ll;
    for (int i = 1; i < N; ++i) {
        C[i][0] = 1ll;
        for (int j = 1; j < N; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
        }
    }
    pw2[0] = 1;
    for (int i = 1; i < N * N; ++i) {
        pw2[i] = pw2[i - 1] * 2ll % p;
    }
    for (int i = 1; i < N; ++i) {
        ll x = (pw2[i] + p - 1) % p;
        pw3[i][0] = 1;
        for (int j = 1; j < N; ++j) {
            pw3[i][j] = 1ll * pw3[i][j - 1] * x % p;
        }
    }
    for (int i = 1; i < N * N; ++i) {
        INV[i] = qpow(pw2[i], p - 2);
    }
}

void up(int &x, int y) {
    x += y;
    if (x >= p) x -= p;
}

void RUN() {
    scanf("%d %d %lld", &n, &m, &p);
    pre();
    memset(f, 0, sizeof f);
    f[0][1][0][1] = 1ll;
    ll res = 0;
    ll inv = qpow(m, p - 2);
    for (int i = 0; i <= n + m; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 0; k <= m; ++k) {
                if (i & 1) {
                    for (int l = 1; l <= k - (i / 2); ++l) {
                        if (f[i][j][k][l] == 0) continue;
                        res = (res + 1ll * i * f[i][j][k][l] % p * inv % p * l % p) % p;
                        for (int o = 1; o + j <=
                                        n; ++o) {//f[i + 1][j + o][k][o] += f[i][j][k][l] * P, P = C[n - j][o] * (2^l - 1)^o/2^l(n-j)
                            up(f[i + 1][j + o][k][o],
                               1ll * f[i][j][k][l] * C[n - j][o] % p * pw3[l][o] % p * INV[l * (n - j)] % p);
                        }
                    }
                } else {
                    for (int l = 1; l <= j - (i / 2); ++l) {
                        if (f[i][j][k][l] == 0) continue;
                        for (int o = 1; o + k <=
                                        m; ++o) {//f[i + 1][j][k + o][o] += f[i][j][k][l]*P, P = C[m - k][o]*(2^l-1)^o/2^l(m-k)
                            up(f[i + 1][j][k + o][o],
                               1ll * f[i][j][k][l] * C[m - k][o] % p * pw3[l][o] % p * INV[l * (m - k)] % p);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", res);
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}