提出 #11875974

---

ソースコード 拡げる

#include <bits/stdc++.h>
typedef long long int ll;
 
using namespace std;
// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
public:
  int64_t a;
 
  explicit constexpr modint(const int64_t x = 0) noexcept :
    a((x % M + M) % M) {}
  constexpr int64_t &value() noexcept { return a; }
  constexpr const int64_t &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= M) {
      a -= M;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += M;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % M;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    int64_t exp = M - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr modint pow(ll t) const {
    if (!t) return modint(1);
    modint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
};
// }}}
using mint = modint<1000000007>;
 
ll N, K;
mint dp[61][64][64];
 
int main() {
  cin >> N >> K;
  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      ll x;
      cin >> x;
      dp[0][i][j] = mint(x);
    }
  }
  for (int k=1; k<61; k++) {
    for (int i=0; i<N; i++) {
      for (int j=0; j<N; j++) {
        for (int u=0; u<N; u++) {
          dp[k][i][j] += dp[k-1][i][u] * dp[k-1][u][j];
          //if (dp[k][i][j].value() > 0) {
          //  printf("dp[%d][%d][%d]=%d\n",k,i,j,dp[k][i][j]);
          //}
        }
      }
    }
  }
  vector<mint> c(N, mint(1));
  for (int k=0; k<61; k++) {
    if (((((ll)1)<<k) & K)) {
      vector<mint> nc(N, mint(0));
      for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
          nc[j] += c[i] * dp[k][i][j];
        }
      }
      c = nc;
    }
  }
  mint ans;
  for (int i=0; i<N; i++) {
    ans += c[i];
  }
  cout << ans.value() << endl;
  return 0;
}

提出情報

ジャッジ結果