Submission #11377991

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

template<typename T,T MOD = 1000000007>
struct Mint{
    T v;
    Mint():v(0){}
    Mint(signed v):v(v){}
    Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

    Mint pow(long long k){
        Mint res(1),tmp(v);
        while(k){
            if(k&1) res*=tmp;
            tmp*=tmp;
            k>>=1;
        }
        return res;
    }

    static Mint add_identity(){return Mint(0);}
    static Mint mul_identity(){return Mint(1);}

    Mint inv(){return pow(MOD-2);}

    Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
    Mint& operator/=(Mint a){return (*this)*=a.inv();}

    Mint operator+(Mint a) const{return Mint(v)+=a;};
    Mint operator-(Mint a) const{return Mint(v)-=a;};
    Mint operator*(Mint a) const{return Mint(v)*=a;};
    Mint operator/(Mint a) const{return Mint(v)/=a;};

    Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

    bool operator==(const Mint a)const{return v==a.v;}
    bool operator!=(const Mint a)const{return v!=a.v;}
    bool operator <(const Mint a)const{return v <a.v;}

    static Mint comb(long long n,int k){
        Mint res(1);
        for(int i=0;i<k;i++){
            res*=Mint(n-i);
            res/=Mint(i+1);
        }
        return res;
    }
};

template<typename T>
struct SquareMatrix{
    
    vector<vector<T>> dat;
    size_t N;
    SquareMatrix() = default;
    SquareMatrix(size_t N, T val = T()):N(N){
        dat = vector<vector<T>> (N, vector<T> (N));
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                dat[i][j]=val;
    }
    SquareMatrix& operator=(const SquareMatrix& a){
        dat=a.dat;
        return (*this);
    }
    bool operator==(const SquareMatrix& a) const{
        return dat==a.dat;
    }

    size_t size() const{return N;};
    vector<T>& operator[](size_t k){return dat[k];};
    const vector<T>& operator[](size_t k) const {return dat[k];};

    SquareMatrix operator*(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                for(size_t k=0;k<N;k++)
                    res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
        return res;
    }

    SquareMatrix operator+(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                res[i][j]=dat[i][j]+B[i][j];
        return res;
    }

    SquareMatrix pow(long long n) const{
        SquareMatrix a=*this;
        SquareMatrix res(N, 0);
        for(size_t i = 0; i < N; i++) res[i][i] = 1;    
        while(n){
            if(n&1) res=res*a;      
            a=a*a;      
            n>>=1;
        }
        return res;
    }
};

using modint = Mint<lint>;

int main() {

  
  lint h, r; cin >> h >> r;
  vector<vector<int>> g(r, vector<int> (r));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < r; j++) {
      cin >> g[i][j];
    }
  }

  SquareMatrix<modint> mat(r);
  // mat[i][j] := i -> j への通り数
  for (int from = 0; from < r; from++) {
    vector<vector<int>> dp((1 << r), vector<int> (r, 0));
    dp[(1 << from)][from] = 1;
    
    for (int bit = 0; bit < (1 << r); bit++) {
      for (int u = 0; u < r; u++) {
        if (dp[bit][u] == 0) continue;
        for (int v = 0; v < r; v++) {
          if (bit & (1 << v)) continue; // すでに訪問済みなら
          if (!g[u][v]) continue;
          (dp[bit | (1 << v)][v] += dp[bit][u]) %= MOD;
        }
      }
    }

    for (int bit = 0; bit < (1 << r); bit++) {
      for (int u = 0; u < r; u++) {
        mat[from][u] += dp[bit][u];
      }
    }
  }

  mat = mat.pow(h);
  cout << mat.dat[0][0].v << endl;
  return 0;
}

Submission Info

Judge Result