FZU 1911 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] << "....
";
        }
    }
    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 << "===
";

        if (sn%2 || sn==0) {
            printf("Case %d: No
", ++cas);
            continue;
        }

        printf("Case %d: Yes
", ++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("
");
        }
    }
    return 0;
}