Loading... [Link](http://codeforces.com/problemset/problem/1228/E) ## Sol 容斥练习题。其实跟 [【JSOI2015】染色问题](https://www.luogu.com.cn/problem/P6076) 差不多,异曲同工之妙。可以先看看那道题。 枚举有多少行没有填 $1$,假设有 $i$ 行,那么这 $i$ 行填数字的方案数是 $(k-1)^i$,剩余 $n-i$ 行的填数字的方案数是 $k^{n-i}$。此外,还应减去全部都没填 $1$ 的方案数:$(k-1)^n$。 这一类题目有一个共同的性质,也是可以像上述那样计算的基础:行和列之间独立。我们刚才那样是填一行的,$n$ 行全填只需要 $n$ 次幂即可。 所以: $$ Ans = \sum\limits_{i=0}^{n} (-1)^i \binom{n}{i} ((k-1)^i \cdot k^{n-i} - (k-1)^n)^n $$ 可以在 $O(n \log n)$ 内的时间计算完。 ## Code ```cpp #include <bits/stdc++.h> #define int long long using namespace std; const int N = 2.5e2, SIZE = N + 5; const int mod = 1e9 + 7; int n, k; int fac[SIZE], inv[SIZE], pw[SIZE], pw1[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } void init() { fac[0] = pw[0] = pw1[0] = 1ll; for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * k % mod, pw1[i] = pw1[i - 1] * (k - 1) % mod; inv[N] = qPow(fac[N], mod - 2ll); for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod; } int C(int x, int y) { if (x < y) return 0ll; return fac[x] * inv[y] % mod * inv[x - y] % mod; } signed main() { n = read(), k = read(); init(); int ans = 0; for (int i = 0; i <= n; ++ i) { int p = qPow(((pw1[i] * pw[n - i] % mod) - pw1[n] + mod) % mod, n) % mod; if (i & 1) ans = (ans - (C(n, i) * p % mod) + mod) % mod; else ans = (ans + (C(n, i) * p % mod)) % mod; } printf("%lld\n", ans); return 0; } ``` 最后修改:2021 年 10 月 07 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏