結果

問題 No.579 3 x N グリッド上のサイクルのサイズ(hard)
ユーザー Newtech66Newtech66
提出日時 2024-08-24 17:16:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 4,441 bytes
コンパイル時間 4,499 ms
コンパイル使用メモリ 240,092 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-08-24 17:16:55
合計ジャッジ時間 8,109 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
lol binexp(lol base,lol power){
    if(power==0)    return 1ll;
    lol res = binexp(base,power/2);
    res = (res*res)%mod2;
    if(power%2==1)  res = (res*base)%mod2;
    return res;
}
 
const int mod = 1'000'000'007;
struct Matrix{
    using ll=long long int;
    vector<vector<ll>> mat;
    Matrix(ll rows,ll cols){
        mat.resize(rows,vector<ll>(cols,0));
    }
    void Init(vector<vector<ll>> values){
        int rows = values.size();
        int cols = values[0].size();
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++){
                mat[i][j] = values[i][j] % mod;
            }
        }
    }
    Matrix add(Matrix &other){
        //beware of dimensions
        Matrix result(mat.size(),mat[0].size());
        for(int i=0; i<mat.size(); i++){
            for(int j=0; j<mat[0].size(); j++)
                result.mat[i][j] = (mat[i][j] + other.mat[i][j])%mod;
        }
        return result;
    }
    Matrix multiply(Matrix &other){
        //beware of dimensions
        ll m = mat.size();
        ll n = other.mat[0].size();
        ll p = other.mat.size();
        if(mat[0].size()!=p){
            return Matrix(0,0);
        }
        Matrix result(m,n);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                ll sum = 0;
                for(int k=0; k<p; k++){
                    sum += (mat[i][k] * other.mat[k][j])%mod;
                    sum %= mod;
                }
 
                result.mat[i][j] = sum;
            }
        }
        return result;
    }
    Matrix expo(ll k){
        if(mat.size()!=mat[0].size()){
            //expo not possible
            return Matrix(0,0);
        }
        ll size = mat.size();
        Matrix result(size,size);
        for(int i=0; i<size; i++)
            result.mat[i][i] = 1;
        Matrix base(size,size);
        base.Init(mat);
        while(k){
            if(k%2)
                result = result.multiply(base);
            base = base.multiply(base);
            k/=2;
        }
        return result;
    }
    Matrix geom(ll k){
        if(mat.size()!=mat[0].size()){
            //expo not possible
            return Matrix(0,0);
        }
        ll size = mat.size();
        Matrix result(size,size);
        Matrix base(size,size);
        base.Init(mat);
        if(k==1){
            return base;
        }
        if(k%2==1){
            Matrix temp = base.expo(k);
            result = result.add(temp);
        }
        k/=2;
        Matrix temp = base.geom(k);
        Matrix temp2 = base.expo(k);
        for(int i=0; i<size; i++){
            temp2.mat[i][i] += 1;
            temp2.mat[i][i] %= mod;
        }
        Matrix temp3 = temp2.multiply(temp);
        result = result.add(temp3);
        return result;
    }
};
 
vector<vector<lol>> M = 
{
    { 1,1,1,0,1,0,0,0,0,0,0,0,1}, // a[n-1]
    { 1,2,1,1,0,0,0,0,0,0,0,0,1}, // b[n-1]
    { 2,2,1,1,0,1,0,0,0,0,0,0,1}, // c[n-1]
    { 0,2,1,1,0,0,0,0,0,0,0,0,1}, // d[n-1]
    { 0,0,1,0,1,0,0,0,0,0,0,0,0}, // e[n-1]
    { 2,0,0,0,0,1,0,0,0,0,0,0,1}, // f[n-1]
    { 2,2,2,0,2,0,1,1,1,0,1,0,4}, // A[n-1]
    { 4,6,2,4,0,0,1,2,1,1,0,0,6}, // B[n-1]
    {12,8,2,6,0,5,2,2,1,1,0,1,8}, // C[n-1]
    { 0,4,2,2,0,0,0,2,1,1,0,0,4}, // D[n-1]
    { 0,0,4,0,4,0,0,0,1,0,1,0,0}, // E[n-1]
    {10,0,0,0,0,4,2,0,0,0,0,1,7}, // F[n-1]
    { 0,0,0,0,0,0,0,0,0,0,0,0,1}, // 1
    // ans is sum over n of 2*A[n]+2*B[n]+C[n]+D[n]+E[n]
};
 
void solve(){
    lol n;
    Matrix res = Matrix(M.size(),M.size());
    res.Init(M);
    cin>>n;
    res = res.geom(n);
    cout<<(2*res.mat[6][12]+2*res.mat[7][12]+res.mat[8][12]+res.mat[9][12]+res.mat[10][12])%mod<<endl;
}
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
// cin>>_;
while(_--)
{
    solve();
}
return 0;
}
0