方格画(CC++)

admin2024-04-03  0

理解题意

ZZX学长在正因街买了一个白色的方格画板, 他想把画板固定在墙上绘画. 白色画板不能转动, 画板上有n×n的网格, ZZX可以选择任意多行及任意多列的格子涂成黑色(选择的整行, 列均需涂成黑色), 所选行数, 列数均可为0.
ZZX希望最终的成品上需要有k个黑色格子, 请告诉ZZX共有多少种涂色方案
注意: 两个方案中任意一个相同位置的格子颜色不同,就视为不同的方案, 若不存在对应的涂色方案, 则为0.


 

数据范围

1<= n <= 60 <= k <= n * n

输入格式:

第一行输入整数n, 第二行输入整数k

输出格式:

输出涂色方案的数量


输入样例:

在这里给出一组输入。例如:

2
2

输出样例:

在这里给出相应的输出。例如:

4

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <iostream>
using namespace std;
int J(int i){                //计算阶乘
    if(i==1||i==0) return 1;
    return i*J(i-1);
}
inline int C(int m,int n){   //计算组合数
    if(n==0||n==m) return 1;
    if(n==1) return m;
    return J(m)/(J(n)*J(m-n));
}
int main(){
    int n,k;
    cin>>n;
    cin>>k;
  int m=k/n;                 //如果列数(行数)为0,至少需要m行(列)
    int cnt=0;
    if(k==n*n){              //铺满
        cout<<"1";
        return 0;
    }
    for(int i=m;i>=0;i--){   
        for(int j=0;j<=m;j++){
          if(n*(i+j)-i*j==k){
              cnt+=C(n,i)*C(n,j);
          }  
        }
    }
cout<<cnt;
}

另外

输入 4  8  输出12

输入 4  10 输出98

计算组合数,格外注意不要计算成排列数

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!