题目链接:Construct a Matrix

题意:构造一个矩阵,要求矩阵的每行每列的和都不相同。矩阵的边长是前n项斐波那契的和。

思路:由sn = 2*(fn-1)+(fn-2)-1,只要知道第n-1和第n-2项即可,n的范围是10^9,可由矩阵快速幂求出第n项。然后,构造矩阵,上三角为1,下三角全为-1,对角线1和0交替。【真是个天才...!!!】矩阵快速幂求第n项时,构造的矩阵是a[0][0] = f2, a[1][0] = f1, a[0][1] = 1, a[1][1] = 0........【ACMer的脑洞真大...可怕....当然不包括我辣...】

知道思路当然就好实现了。附代码:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std; struct Mat{
int a[2][2];
void init1() { // 斐波那契初始矩阵
a[0][0] = a[0][1] = a[1][0] = 1;
a[1][1] = 0;
}
void init2() { //单位矩阵
a[0][0] = a[1][1] = 1;
a[0][1] = a[1][0] = 0;
}
}; Mat mul(Mat aa, Mat b, int m) { // 矩阵乘法mod m
Mat ans;
for (int i=0; i<2; ++i) {
for (int j=0; j<2; ++j) {
ans.a[i][j] = 0;
for (int k=0; k<2; ++k) {
ans.a[i][j] += ((aa.a[i][k]%m)*(b.a[k][j]%m))%m;
ans.a[i][j] %= m;
//ans.a[i][j] += aa.a[i][k]*b.a[k][j];
}
//cout << ans.a[i][j] << "....\n";
}
}
return ans;
} Mat mul_mat_quick(Mat a, int n, int m) { // 矩阵快速幂%m
Mat ans;
ans.init2();
while(n) {
if (n%2) ans = mul(ans, a, m);
a = mul(a, a, m);
n /= 2;
}
return ans;
} int num[210][210]; int main() {
int t;
int cas = 0;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
Mat a;
a.init1();
Mat ans = mul_mat_quick(a, n-1, m);
int fn1 = ans.a[0][0]; // fn-1
int fn2 = ans.a[1][0]; // fn-2
//cout << fn1 << "++++=" << fn2 << endl;
int sn = (2*fn1 + fn2 - 1)%m; //矩阵边长
// cout << sn << "===\n"; if (sn%2 || sn==0) {
printf("Case %d: No\n", ++cas);
continue;
} printf("Case %d: Yes\n", ++cas);
memset(num, 0, sizeof(num));
for (int i=1; i<=sn; ++i) {
for (int j=1; j<=sn; ++j) {
if (i<j) num[i][j] = 1;
else num[i][j] = -1;
}
}
int pre = 1;
for (int i=1; i<=sn; ++i) {
num[i][i] = (pre^1);
pre ^= 1;
}
for (int i=1; i<=sn; ++i) {
for (int j=1; j<=sn; ++j) {
if (j==1) printf("%d", num[i][j]);
else printf(" %d", num[i][j]);
}
printf("\n");
}
}
return 0;
}

  

05-11 09:34
查看更多