【阶乘】个人练习-Leetcode-LCP 22. 黑白方格画

题目链接：https://leetcode.cn/problems/ccw6C7/description/

题目大意：给出一块白方格面积为n*n，给出一个数字k，每一次操作可以把方格的某一整行或者某一整列涂黑，求使得黑色格子数字为k的【最终图案】的个数。

思路：虽然是简单题，但还想了一会的。因为【最终图案数】并不是【操作方法数】。比如2*2的格子，【先涂一行再涂一列】和【先涂一列再涂一行】得到的图案是一样的。我们发现涂的行列具体是哪几行哪几列并不影响最终黑格子的数目，因此可以先得出【需要涂黑x行】和【需要涂黑y列】，然后求组合数$C_n^x$和$C_n^y$的乘积即可。因为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];elsereturn 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;}
};