题意 给定n个点，任意两点之间可以不连边也可以连边。如果连边的话可以染上m种颜色。
求最后形成的图，是一个带环连通图的方案数。
首先答案是n个点的图减去n个点能形成的树。
n个点能形成的树的方案数比较好求，根据prufer序列可以知道n个点形成的无根树的个数为$n^{n-2}$
那么现在问题变成求n个点形成的连通图的个数。
图有连通和不连通的，那么就是图的总数减去不连通的图的总数。
图的总数很简单，$m^{\frac{n(n-1)}{2}}$，那么现在要求不连通的图的总数。
设$f(n)$为$n$个点的不连通的图的总数
$f(n) = ∑f(i) * C(n - 1, i - 1) * f(n - i)$，$i$从$1$到$n-1$。
这是一个卷积的形式，可以分治NTT来求，就可以了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define fi first
#define se second
#define MP make_pair typedef long long LL; const LL G = 106;
const LL mod = 152076289;
const LL N = 4e4 + 10; int T;
int ca = 0; LL x1[N], x2[N];
LL ans;
LL n, m;
LL f[N], g[N], h[N];
LL c[N], fac[N], ifac[N]; LL Pow(LL a, LL b){
LL ret = 1;
while (b){
if (b & 1) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
} void change (LL *y, int len){
int i, j, k;
for (i = 1, j = len / 2; i < len - 1; i++) {
if (i < j) swap(y[i], y[j]);
k = len / 2;
while (j >= k) {
j -= k;
k /= 2;
}
if (j < k) j += k;
}
} void ntt (LL *y, int len, int on) {
change (y, len);
int id = 0;
for(int h = 2; h <= len; h <<= 1) {
id++;
LL wn = Pow (G, (mod - 1) / (1<<id));
for(int j = 0; j < len; j += h) {
LL w = 1;
for(int k = j; k < j + h / 2; k++) {
LL u = y[k] % mod;
LL T = w * (y[k + h / 2] % mod) % mod;
y[k] = (u + T) % mod;
y[k + h / 2] = ((u - T) % mod + mod) % mod;
w = w * wn % mod;
}
}
}
if (on == -1){
for (int i = 1; i < len / 2; i++)
swap (y[i], y[len - i]);
LL inv = Pow(len, mod - 2);
for(int i = 0; i < len; i++)
y[i] = y[i] % mod * inv % mod;
}
} void solve(int l, int r){
if (l == r){
f[l] += g[l];
f[l] %= mod;
return;
} int mid = (l + r) >> 1;
solve(l, mid);
int len = 1;
while (len <= r - l + 1) len <<= 1;
rep(i, 0, len - 1) x1[i] = x2[i] = 0; rep(i, l, mid) x1[i - l] = f[i] * ifac[i - 1] % mod;
rep(i, 1, r - l) x2[i - 1] = g[i] * ifac[i] % mod; ntt(x1, len, 1);
ntt(x2, len, 1);
rep(i, 0, len - 1) x1[i] = x1[i] * x2[i] % mod;
ntt(x1, len, -1);
rep(i, mid + 1, r){
f[i] -= x1[i - l - 1] % mod * fac[i - 1] %mod;
(f[i] += mod) %= mod;
}
solve(mid + 1, r);
} int main(){ fac[0] = 1;
rep(i, 1, N - 1) fac[i] = fac[i - 1] * i % mod;
ifac[N - 1] = Pow(fac[N - 1], mod - 2);
dec(i, N - 2, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod; scanf("%d", &T);
while (T--){
scanf("%lld%lld", &n, &m);
memset(f, 0, sizeof f);
rep(i, 1, n) g[i] = Pow(m + 1, 1ll * i * (i - 1) / 2);
solve(1, n);
ans = (f[n] - Pow(n, n - 2) * Pow(m, n - 1) % mod + mod) % mod;
printf ("Case #%d: %lld\n", ++ca, ans);
} return 0;
}