- 科技
- codeforces997C 组合计数（容斥原理）
题意：一个N*N的的方格，一共有三中颜色，进行填涂，两种填涂方案不同当且仅当存在大于一个格子的颜色不同，问所有的填涂方案中有多少存在行是同种颜色或者列是同种颜色的方案数。
思路：直接求是行不通的，考虑总共的方案数是3^n*2 ，减去不存在相同颜色行列的方案数。
减去每一列都没有颜色相同的方案数（3 ^ n-3）^n;但是这里面包含了有存在行颜色相同的，即我多减了部分
加上有一行有颜色相同的方案数
C（n,1) * (3 * (3^(n-1) - 1) ^n) , 但是有重复计数，应减去其中至少有两行的方案数
…………
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const int N
= 1e6+5;
const ll mod
= 998244353;
ll f
[N
],inv
[N
],c
[N
];
ll
qpow(ll a
,ll n
){
if(a
== 0) return 0;
ll res
= 1;
while(n
){
if(n
%2) res
= a
%mod
*(res
%mod
)%mod
;
a
= a
%mod
*(a
%mod
)%mod
;
n
>>= 1;
}
return res
;
}
int main(){
ll n
;
scanf("%lld",&n
);
f
[0] = 1;
for(ll i
= 1 ; i
<= n
; i
++) f
[i
] = (i
*f
[i
-1])%mod
;
inv
[1] = 1;
for(ll i
= 2 ; i
<= n
; i
++) inv
[i
] = (mod
- mod
/i
)*inv
[mod
%i
]%mod
;
inv
[0] = 1;
for(ll i
= 1 ; i
<= n
; i
++) inv
[i
] = inv
[i
]*inv
[i
-1]%mod
;
for(ll i
= 1 ; i
<= n
; i
++) c
[i
] = f
[n
]*inv
[n
-i
]%mod
*inv
[i
]%mod
;
ll ans
= (qpow(3,n
*n
) - qpow(qpow(3,n
)-3,n
)+mod
)%mod
;
for(ll i
= 1 ; i
<= n
; i
++){
if(i
%2ll) ans
= (ans
+ c
[i
]*3%mod
*qpow(qpow(3,n
-i
)-1,n
)%mod
+ c
[i
]*(qpow(3,i
)-3+mod
)%mod
*(qpow(3,n
*(n
-i
)))%mod
)%mod
;
else ans
= (ans
- c
[i
]*3%mod
*qpow(qpow(3,n
-i
)-1,n
)%mod
- c
[i
]*(qpow(3,i
)-3+mod
)%mod
*(qpow(3,n
*(n
-i
)))%mod
+ 10ll*mod
)%mod
;
}
printf("%lld\n",ans
);
return 0;
}
Processed:
0.026, SQL:
8
