AtCoder ABC 242 pF. Black and White Rooks 解題心得( 題目 )
解題概念:DP、排列組合
解題方法:在解題之前，先思考一個性質:如果這行有白色的，那就不能有黑色，我們可以先討論個DP[i][j]，定義他代表我放了某個顏色的棋子(假設a個)後，(1)可以把他放入一個i*j的長方形，(2)裡面每排每列都有至少一個棋子的方法數，那這個值怎麼求呢?
我們可以用C(i*j,a)代表他，可是顯然DP[i][j]不會等於C(i*j,a)，因為有些情況並沒有符合條件(2)，所以我們得扣除前面的DP乘上組合數。
我們可在O(N^2M^2)算出表格，但是求出DP能幹嘛呢，我們注意到DP代表他的排列方式，假設我們已經做出兩個表格W、B，則我們可以枚舉W[i][j]、B[k][l]的組合，注意i+k<n，j+l<m都符合!可是怎麼算呢?
我們前面算的DP是正方形，但是我們把它轉成從開始的棋盤選出i列j行，接著剩下的棋盤列行選出k列l行，也就是枚舉i、j、k、l，將所有B[i][j]*B[k][l]*C(N,i)*C(M,j)*C(N-i,k)*C(M-j,l) 加總!!
Java參考程式碼(更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/03/09
import java.util.*;
import java.io.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,rd;
public static final long p=998244353;
public static long[] fac=new long[2505];
public static long[] inv=new long[2505];
public static long[][] db=new long[55][55];
public static long[][] dw=new long[55][55];
public static void main(String[] args) throws Exception{
final int N=readint();
final int M=readint();
final int B=readint();
final int W=readint();
init();
long cnt=0,ans=0;
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
cnt=0;
for(int k=1;k<=i;k++) {
for(int l=1;l<=j;l++) {
cnt+=(db[k][l]*pi(j,l)%p*pi(i,k))%p;
cnt%=p;
}
}
db[i][j]=per(i,j,B)-cnt+p*10;
db[i][j]%=p;
}
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
dw[i][j]=cnt=0;
for(int k=1;k<=i;k++) {
for(int l=1;l<=j;l++) {
cnt+=(dw[k][l]*pi(j,l)%p*pi(i,k))%p;
cnt%=p;
}
}
dw[i][j]=per(i,j,W)-cnt+p*10;
dw[i][j]%=p;
}
}
for(int i=1;i<N;i++) {
for(int j=1;j<M;j++) {
for(int k=N-i;k>0;k--) {
for(int l=M-j;l>0;l--) {
ans+=(db[i][j]*dw[k][l]%p*pi(N,i)%p*pi(M,j)%p*pi(N-i,k)%p*pi(M-j,l)%p);
ans%=p;
}
}
}
}
System.out.println(ans);
}
public static long per(int x,int y,int n) {
if(n>x*y)return 0;
return fac[x*y]*inv[n]%p*inv[x*y-n]%p;
}
public static long pi(int m,int n) {
return fac[m]*inv[n]%p*inv[m-n]%p;
}
public static void init() {
fac[0]=1;
for(int i=1;i<2505;i++) {
fac[i]=fac[i-1]*i;
fac[i]%=p;
}
for(int i=0;i<2505;i++) {
inv[i]=fast(fac[i],p-2);
}
}
public static long fast(long x,long pw) {
if(pw<=1) {
return x;
}
if((pw&1)==0) {
long ret=fast(x,pw>>1);
return ret*ret%p;
}
else {
long ret=fast(x,pw>>1);
return ret*ret%p*x%p;
}
}
public static int readint() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
留言列表
