A31430. 吉利矩阵
填空题
中等
知识点
题目描述
吉利矩阵
题目描述
所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？
输入格式
输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。
输出格式
在一行中输出满足题目要求条件的方阵的个数。
输入样例
7 3
输出样例
666
参考答案
#include <iostream>
using namespace std;
int l, n, ans;
int xx[5], yy[5];
void dfs(int);
int main() {
cin >> l >> n;
dfs(0);
cout << ans;
return 0;
}
void dfs(int idx) {
if (n * n == idx) {
ans ++;
return;
}
for (int i = 0; i <= l; i ++) {
int x, y;
x = idx / n;
y = idx % n;
if (xx[x] + i > l || yy[y] + i > l) continue;
if (x == n - 1 ) i = l - yy[y];// if (x == n - 1 && yy[y] + i < l) continue;本来是这个，但是我们可以直接让i等于我们需要的那个值。两种都可以过
if (y == n - 1 ) i = l - xx[x];
xx[x] += i;
yy[y] += i;
dfs(idx + 1);
xx[x] -= i;
yy[y] -= i;
}
}答案解析
#include<iostream>
using namespace std;
const int N=20;
int a[N][N];
int main() {
int l,n;
cin>>l>>n;
a[2][2]=3;
a[2][3]=21;
a[2][4]=282;
a[3][2]=4;
a[3][3]=55;
a[3][4]=2008;
a[4][2]=5;
a[4][3]=120;
a[4][4]=10147;
a[5][2]=6;
a[5][3]=231;
a[5][4]=40176;
a[6][2]=7;
a[6][3]=406;
a[6][4]=132724;
a[7][2]=8;
a[7][3]=666;
a[7][4]=381424;
a[8][2]=9;
a[8][3]=1035;
a[8][4]=981541;
a[9][2]=10;
a[9][3]=1540;
a[9][4]=2309384;
cout<<a[l][n];
}
上一题
下一题