【阶乘】个人练习-Leetcode-LCP 22. 黑白方格画
题目链接:https://leetcode.cn/problems/ccw6C7/description/
题目大意:给出一块白方格面积为n*n
,给出一个数字k
,每一次操作可以把方格的某一整行或者某一整列涂黑,求使得黑色格子数字为k
的【最终图案】的个数。
思路:虽然是简单题,但还想了一会的。因为【最终图案数】并不是【操作方法数】。比如2*2的格子,【先涂一行再涂一列】和【先涂一列再涂一行】得到的图案是一样的。我们发现涂的行列具体是哪几行哪几列并不影响最终黑格子的数目,因此可以先得出【需要涂黑x
行】和【需要涂黑y
列】,然后求组合数
C
n
x
C_n^x
Cnx和
C
n
y
C_n^y
Cny的乘积即可。因为x, y
对可能有多个,我们用一个vector<pair<int, int>>
来保存。
然而要注意一下一些特殊情况:
k < n
:那么就算只涂一行也会超过,不行
k == 0
:什么都不用做,返回1
求阶乘的话可以用一个数组来保存结果,避免重复计算。
完整代码
class Solution {
public:
vector<int> frac;
int getFrac(int x) {
if (x == 0)
return frac[0] = 1;
if (frac[x])
return frac[x];
else
return frac[x] = x*getFrac(x-1);
}
int paintingPlan(int n, int k) {
if (k == 0)
return 1;
if (n > k)
return 0;
if (n*n == k)
return 1;
int ans = 0;
vector<pair<int, int>> res;
frac.resize(n+1, 0);
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (x*n+y*(n-x) > k)
break;
else if (x*n+y*(n-x) == k) {
res.emplace_back(make_pair(x, y));
}
else;
}
}
for (auto p : res) {
int x = p.first, y = p.second;
ans += (getFrac(n)/getFrac(x)/getFrac(n-x)) * (getFrac(n)/getFrac(y)/getFrac(n-y));
}
return ans;
}
};
原文地址:https://blog.csdn.net/Rstln/article/details/140436422
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!