题解 CF997C 【Sky Full of Stars】

command_block

2019-10-27 20:27:32

Solution

大家好像都是考虑容斥,咱这里有个不需要费脑子的二项式反演…… ------------ **题意** : 有一个正方形网格,用三种颜色染。 求有多少种方案使得**至少**一行或一列是同一种颜色。 结果对大质数取模。 按照套路: 令$F(i,j)$为**钦定**有$i$行$j$列是**同种**颜色,**其余任意**的方案数。 令$G(i,j)$为**恰好**有$i$行$j$列是**同种**颜色的方案数。 我们要求的就是 : 全集$-G(0,0)$ 容易得到$F(x,y)=\sum\limits_{i=x}^n\sum\limits_{j=y}^n\dbinom{i}{x}\dbinom{j}{y}G(i,j)$ 然后采用**高维二项式反演**(请见[Link](https://www.luogu.org/blog/command-block/yi-suo-ji-guai-di-fan-yan)): $G(x,y)=\sum\limits_{i=x}^n\sum\limits_{j=y}^n(-1)^{i+j-x-y}\dbinom{i}{x}\dbinom{j}{y}F(i,j)$ ------------ 再来算$F(i,j)$,这需要分类讨论。 - 当两个参数都不为0时,所有被钦定的行和列**必须是同种颜色**。 $F(i,j)=\dbinom{n}{i}\dbinom{n}{j}3*3^{(n-i)(n-j)}$ 即 : 选定行列 X 钦定颜色 X 放任自流 - 当任意一个参数为0时,被钦定的行或列不用一定是同种颜色。 $F(i,0)=\dbinom{n}{i}3^i*3^{n(n-i)}$ - 两个参数都为0 完全放任,$F(0,0)=3^{n^2}$ ------------ 根据前面的反演: $G(0,0)=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-1)^{i+j}F(i,j)$ 再分三个部分求和: - 当两个参数都不为0的贡献 $=\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}\dbinom{n}{i}\dbinom{n}{j}3*3^{(n-i)(n-j)}$ $=3^{n^2+1}\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}\dbinom{n}{i}\dbinom{n}{j}3^{-in-jn+ij}$ $=3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{-jn}3^{ij}$ 我们发现这个$3^{ij}$项十分讨厌,导致前后两个$\sum$有了关联,不能直接用二项式定理…… 数据范围为$10^6$,只需要消掉一个$\sum$,还是有办法对付的。 $=3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{j(i-n)}$ 现在观察后面的$\sum\limits_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{j(i-n)}$就可以二项式定理了。 $this=\sum\limits_{j=1}^n\dbinom{n}{j}1^{n-j}(-3^{(i-n)})^{j}=(1-3^{(i-n)})^n-1$ 注意求和下标不到0,最后要减去$1$. 回代可得: $=3^{n^2+1}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}((1-3^{(i-n)})^n-1)$ 快速幂就可以$O(nlogn)$计算了。 - 当某一个参数都为0的贡献 $i,j$为0本质相同,我们不妨只计$i$,然后贡献翻倍即可。 (其实是可以直接快速幂暴力,不过为了常数还是推一下式子吧) $=2\sum\limits_{i=1}^n(-1)^{i}\dbinom{n}{i}3^i*3^{n(n-i)}$ $=2*3^{n^2}\sum\limits_{i=1}^n\dbinom{n}{i}(-1)^{i}3^i*3^{-in}$ $=2*3^{n^2}\sum\limits_{i=1}^n\dbinom{n}{i}(-3^{(1-n)})^{i}$ $=2*3^{n^2}((1-3^{(1-n)})^n-1)$(注意这里求和下标也不到0) - 两个参数都为0的贡献 $=3^{n^2}=$全集 又因为$ANS=$全集$-G(0,0)$ 我们发现,直接给前两部分贡献变号就能够得到答案了。 ------------ **Code:** 复杂度$O(nlogn)$. 为了跑得快一点,使用了光速幂。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define mod 998244353 #define tod 998244352 #define MaxN 1005000 using namespace std; ll powM(ll a,int t) { ll ans=1; while(t){ if(t&1)ans=ans*a%mod; a=a*a%mod; t>>=1; }return ans; } int n; ll fac[MaxN],ifac[MaxN],pw[35000],pw2[35000]; ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;} ll pow3(int t) {return pw2[t>>15]*pw[t&32767]%mod;} void Init() { fac[0]=ifac[0]=ifac[1]=1; for (int i=2;i<=n;i++) ifac[i]=(ifac[mod%i]*(mod-mod/i))%mod; for (int i=1;i<=n;i++){ fac[i]=fac[i-1]*i%mod; ifac[i]=ifac[i]*ifac[i-1]%mod; }pw[0]=pw2[0]=1; for (int i=1;i<=32767;i++) pw[i]=pw[i-1]*3%mod; ll buf=pw[32767]*3%mod; for (int i=1;i<=31000;i++) pw2[i]=pw2[i-1]*buf%mod; } int main() { scanf("%d",&n); Init(); ll ans=0,sav; for (int i=1;i<=n;i++){ sav=C(n,i)*pow3(1ll*(tod-i)*n%tod)%mod *(powM(1-pow3(i-n+tod),n)-1)%mod; if (i&1)ans=(ans-sav)%mod; else ans=(ans+sav)%mod; }ans=ans*pow3((1ll*n*n+1)%tod)%mod; ans=(ans+2*pow3(1ll*n*n%tod)%mod *(powM(1-pow3(tod+1-n),n)-1))%mod; printf("%I64d",(mod-ans)%mod); return 0; } ```