哪个网站可以做条形码,天津网站建设制作免费,怎么样制作网站,阿里巴巴外发加工网珠海题目链接#xff1a;https://leetcode.cn/problems/ccw6C7/description/
题目大意#xff1a;给出一块白方格面积为n*n#xff0c;给出一个数字k#xff0c;每一次操作可以把方格的某一整行或者某一整列涂黑#xff0c;求使得黑色格子数字为k的【最终图案】的个数。
思路…题目链接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对可能有多个我们用一个vectorpairint, int来保存。
然而要注意一下一些特殊情况 k n那么就算只涂一行也会超过不行 k 0什么都不用做返回1
求阶乘的话可以用一个数组来保存结果避免重复计算。
完整代码
class Solution {
public:vectorint 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;vectorpairint, int res;frac.resize(n1, 0);for (int x 0; x n; x) {for (int y 0; y n; y) {if (x*ny*(n-x) k)break;else if (x*ny*(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;}
};
