class Solution {
public:
int paintingPlan(int n, int k) {
}
};
LCP 22. 黑白方格画
小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 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 <= 60 <= k <= n * n原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-27 15:01:57
func paintingPlan(n int, k int) int {
if k == 0 || k == n*n {
return 1
}
if k < n {
return 0
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
sum := i*n + j*n - i*j
if sum == k {
x := factorial(n, i)
y := factorial(n, j)
ans += x * y
}
}
}
return ans
}
func factorial(n int, m int) int {
ans := 1
for i := n; i > m; i-- {
ans *= i
}
for i := n - m; i > 0; i-- {
ans /= i
}
return ans
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-27 15:01:22
class Solution {
public:
int fun(int x,int y) //求C（x,y）
{
if(y==0) return 1;
if(y<0) return 0;
int m=1,n=1,z=x-y+1;
while(x>=z)
{
m*=x;
x--;
}
while(y>0)
{
n*=y;
y--;
}
return m/n;
}
int paintingPlan(int n, int k) {
if(k==0) return 1;
if(k<n) return 0;
if(k==n*n) return 1;
float i; //行
float j; //列
int res=0;
for(i=0;i<n;i++)
{
float x=(k-n*i )/(n-i);
if(x!=(int)x) //判断x是否为整数
continue;
j=(int)x;
res+=fun(n,i)*fun(n,j);
}
return res;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.2 MB, 提交时间: 2023-09-27 15:00:33
class Solution {
public int paintingPlan(int n, int k) {
int res = 0;
//边界问题
if(k == 0)return 1;
if(k == n * n)return 1;
//第一层循环表示涂 i 行 第二层循环表示涂 j 列
for(int i = 0;i <= n;i++){
for(int j = 0;j <= n;j++)
//当你涂了 i 行 j 列 则有 i * n + j * n个方格被涂过了
//去掉重复计入的 i*j个方格 是否等于结果k
if((i*n) + (j*n) - (i*j) == k) {
res += C(i,n) * C(j,n);
}
}
return res;
}
//数学里的排列组合 C(愚蠢式写法，勿计较)
public int C(int x,int y){
if(x == 0)return 1;
int n = 1;
for(int i = 0;i < x;i++){
n *= (y - i);
}
for(int i = 1;i <= x;i++){
n /= i;
}
return n;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 13.5 MB, 提交时间: 2020-12-01 00:12:41
class Solution:
def paintingPlan(self, n: int, k: int) -> int:
if k == 0 or k == n*n: return 1
# 阶乘
def helper(n: int):
if n == 0: return 1
return n * helper(n-1)
# 组合
def permuation(n: int, a: int):
return helper(n)//helper(a)//helper(n-a)
ans = 0
# i行j列，求组合
for i in range(n):
for j in range(n):
if (i+j)*n - (i*j) == k:
ans += permuation(n, i) * permuation(n, j)
return ans