|
AC #include<cstdio> #define pr printf #define ll long long #define fo(i, x, y) for(int i = x; i <= y; i ++) #define fd(i, x, y) for(int i = x; i >= y; i --) using namespace std; const int N = 1e6 + 5; int T, n, m, k, ans; ll fac[N], nf[N]; const int mo = 1000109107; ll ksm(ll x, ll y) { ll s = 1; for(; y; y /= 2, x = x * x % mo) if(y & 1) s = s * x % mo; return s; } ll C(int n, int m) { if(n < m || n < 0 || m < 0) return 0; return fac[n] * nf[m] % mo * nf[n - m] % mo; } ll f[4]; ll s(int k) { int p = n + 1 >> 1; int x = n / 2; if(k == 0) { return C(n - 1, m - 1); } else if(k == 1) { return (C(n - p, m - 2) * (p - 1) % mo + C(n - p, m - 1)) % mo * m % mo; } else if(k == 2) { return (C(n - p + 1, m - 1) + C(n - p, m - 1)) % mo * m % mo; } else { if(m != 3) return 0; return C(n - p + 1, m - 1) % mo; } } int main() { freopen('polygon.in', 'r', stdin); freopen('polygon.out', 'w', stdout); n = 1e6; fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo; nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo; scanf('%d', &T); fo(ii, 1, T) { scanf('%d %d %d', &n, &m, &k); if(k > 3) { pr('0\n'); continue;} ll ans = 0; fo(i, k, 3) ans += (i - k & 1 ? -1 : 1) * C(i, k) * s(i) % mo; ans = (ans % mo * n % mo * ksm(m, mo - 2) % mo + mo) % mo; pr('%lld\n', ans); } } 本文作者：Cold_Chair(已授权发布) |
|
|
