#每日一题 力扣第22题 黑白格子画

今天同样是一道双变量的题目，通过行数和列树来控制总的黑色格子数。

小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），所选行数、列数均可为 0。
小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。
注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。
示例 1：
输入：n = 2, k = 2
输出：4
解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。

因为是两个变量，我们采用“定一变一”的方法来设置遍历，先定行数p，行数p可以涂上n*p个有效黑色块，列数q可以涂上（n-p)*q个有效黑色块。然后确定了p和q之后，计算组合数C(n,p)*C(n,q)

class Solution {
public://计算组合数C(n,x)int fun(int x,int n){int a=1,b=1;for(int i=n;i>(n-x);i--)a*=i;for(int i=1;i<=x;i++)b*=i;return a/b;}int paintingPlan(int n, int k) {//根据题目，当整个画布都被涂满时，只有一种方案if(k==n*n)return 1;int temp=0;//先定行数for(int p=0;p<=n;p++){if(p*n>k)break;//再定列数for(int q=0;q<=n;q++){if(p*n+q*(n-p)==k){//将此方案数记录下来temp+=(fun(p,n)*fun(q,n));break;}}}  return temp;         }
};

此方案的时间复杂度为O(n^2)，那能不能想办法降低时间复杂度呢，我们发现根据p可以直接定出q，q=(k-p*n)/（n-p）,这样就可以降为O(n)。
代码如下：

class Solution {
public:int fun(int x,int n){int a=1,b=1;for(int i=n;i>(n-x);i--)a*=i;for(int i=1;i<=x;i++)b*=i;return a/b;}int paintingPlan(int n, int k) {if(k==n*n)return 1;int temp=0;for(int p=0,q=0;p<=n;p++){if(p*n>k)break;//直接根据行数p计算出对应的列数qif((k-p*n)%(n-p)==0){q=(k-p*n)/(n-p);if(q<=n)temp+=(fun(p,n)*fun(q,n));}}  return temp;         }
};