题目

有一个$n\times n$的矩阵，每个格子可以染三种颜色，现在问至少有一行或一列为同色的方案数。

Solution

首先发现只有行和只有列的情况要单独算，因为不相交。

然后考虑既有行，也有列的情况，首先有个$O(n^2)$的容斥应该比较好想：
$$
\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}\binom{n}{i}\binom{n}{j}3^{(n-i)(n-j)+1}
$$
开始以为两个数相乘，指数也相乘了，于是将式子拆开调了一晚上的NTT。

现在重新来看这个式子，它可以表示为如下形式：
$$
\sum_{i=1}^n3(-1)^i\binom{n}{i}\sum_{j=0}^{n-1}(-1)^j\binom{n}{j}3^{(n-i)(n-j)}
$$
它还可以变成如下形式（将$j$变成$n-j$）：
$$
\sum_{i=1}^n3(-1)^i\binom{n}{i}\sum_{j=0}^{n - 1}\binom{n}{j}(-1)^{n-j}(3^{n-i})^j
$$
当我们令$3^{n-i}=c$后，后面那坨式子就可以变成：
$$
\sum_{j=0}^{n - 1}\binom{n}{j}(-1)^{n-j}c^j
$$
根据二项式定理又等价为：
$$
(c-1)^n-c^n
$$
这样就可以$O(n)$算了（如果不是光速幂的话，可能是$O(n\log n)$的）。

记得把只有行或列的方案算进取。

Code

#include <bits/stdc++.h>
#define LL long long
#define PII pair<LL, LL>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 3e6 + 5, mod = 998244353, inv2 = (mod + 1) >> 1;
int n, m;
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 1ll * res * x % mod;
        k >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}
int ans;
int fac[N], inv[N];
inline void init()
{
    fac[0] = 1;
    for(int i = 1;i < N;i ++) fac[i] = 1ll * i * fac[i - 1] % mod;
    inv[0] = inv[1] = 1;
    for(int i = 2;i < N;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    for(int i = 2;i < N;i ++) inv[i] = 1ll * inv[i] * inv[i - 1] % mod;
}
inline int C(int x, int y)
{
    if(y < 0 || x < y) return 0;
    return 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;
}
int main()
{
    init();
    read(n);
    for(int i = 1, res;i <= n;i ++)
    {
        res = qpow(qpow(3, n - i) - 1, n) - qpow(3, 1ll * n * (n - i) % (mod - 1));
        res = 1ll * res * C(n, i) % mod * 3 % mod;
        if(!(i & 1)) res = -res;
        ans = (ans + res) % mod;
    }
    for(int i = 1, flag;i <= n;i ++)
    {
        flag = (i & 1) ? 1 : -1;
        ans = (ans + 2ll * flag * C(n, i) % mod * qpow(3, i) % mod * qpow(3, (1ll * n * n - 1ll * n * i) % (mod - 1))) % mod;
    }
    ans = (ans + mod) % mod;
    write(ans);
    return 0;
}

Luckyleaves's Blog

CF997C Sky Full of Stars

题目

Solution

Code