小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），所选行数、列数均可为 0。

小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

(相关资料图)

示例 1：

输入：n = 2, k = 2

输出：4

解释：一共有四种不同的方案：

第一种方案：涂第一列；

第二种方案：涂第二列；

第三种方案：涂第一行；

第四种方案：涂第二行。

示例 2：

输入：n = 2, k = 1

输出：0

解释：不可行，因为第一次涂色至少会涂两个黑格。

示例 3：

输入：n = 2, k = 4

输出：1

解释：共有 2*2=4 个格子，仅有一种涂色方案。

限制：

1 <= n <= 6

0 <= k <= n * n

依次遍历，判断对应的行数跟列数是否等于k，然后求C(I,N)也就是高中数学里面的排列组合的问题，求出即可；

public class Lcp22 {

public static void main(String[] args) {

System.out.println(paintingPlan(1,0));

System.out.println(c(1, 2));

}

public static int paintingPlan(int n, int k){

if(k==0){

return 0;

}

if(k==n*n){

return 1;

}

int cnt=0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

if(i*n+j*n-i*j==k){

cnt+=c(i,n)*c(j,n);

}

}

}

return cnt;

}

public static int c(int k,int n){

if(k==0){

return 1;

}

if(k==n){

return 1;

}

if(k>n/2){

return c(n-k,n);

}

int mul=1;

for (int i = 0; i < k; i++) {

mul=mul*(n-i);

}

int div=1;

for (int i = 0; i < k; i++) {

div=div*(1+i);

}

return mul/div;

}

}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.3 MB, 在所有 Java 提交中击败了44.64%的用户

关键词：