ZJNU 1228 - 矩阵构造——高级 （矩阵快速幂、构造）

ZJNU 1228 - 矩阵构造——高级

题面

要求构造下面的矩阵：

1. 矩阵的大小为\(S(n)*S(n)\)；
2. \(S(n)\)?表示Fibonacci数列前\(n\)?项和对\(m\)?取模之后的值，即\(S(n)=(F_1+F_2+…+F_n)%m\)?；
3. 矩阵仅由\(-1,0,1\)三种值构成
4. 矩阵每一行每一列的和都不相同

\(F_1=F_2=1\)?；?

给定\(n\)和\(m\)，输出这样一个矩阵。

思路

做法应当有很多种，但由于没有SPJ所以输出必须得与样例的想法相同（可恶）

首先就是斐波那契前\(n\)项前缀和对\(m\)?取模，矩阵快速幂求出即可

记接下来的\(n\)就是构造的矩阵边长

稍微小范围打表可得\(n\)为奇数时或者\(n=0\)?时不存在解

否则根据以下方式构造（难讲）

\(n=2\)时：

\(n=4\)时：

\(n=6\)时：

\(n=8\)时：

#include
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'\n';}templatevoid debug(T x,Args... args){cerr<<"[ "<(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

struct quickpow_fibonacci
{
    struct matrix
    {
        ll n,m,data[3][3];
        void init()
        {
            for(int i=0;i0)
                {
                    for(int j=0;j0)
        {
            if(n&1)
                r=multi(r,a);
            a=multi(a,a);
            n>>=1;
        }
        return r;
    }
    ll solve(ll n)
    {
        matrix a,b;
        a.n=1;
        a.m=3;
        a.data[0][0]=1;
        a.data[0][1]=1;
        a.data[0][2]=1;
        b.n=3;
        b.m=3;
        b.data[0][0]=0;
        b.data[0][1]=1;
        b.data[0][2]=0;
        b.data[1][0]=1;
        b.data[1][1]=1;
        b.data[1][2]=1;
        b.data[2][0]=0;
        b.data[2][1]=0;
        b.data[2][2]=1;
        b=fast_mod(b,n-1);
        return multi(a,b).data[0][2];
    }
}f;

int ans[205][205];

void solve()
{
    ll n;
    cin>>n>>mod;
    n=f.solve(n);
    if(n==0||n%2)
    {
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
    rep(i,1,n/2)
    {
        rep(j,1,n-i+1)
            ans[i][j]=-1;
        rep(j,n-i+2,n)
            ans[i][j]=0;
    }
    rep(i,n/2+1,n)
    {
        rep(j,1,n+1-i)
            ans[i][j]=0;
        rep(j,n+1-i+1,n)
            ans[i][j]=1;
    }
    per(j,n,1)
        per(i,n,1)
            cout<<-ans[i][j]<<(i==1?'\n':' '); // 输出方式改一改对正确性不影响
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}