Submission #11875974


Source Code Expand

Copy
#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;
}

Submission Info

Submission Time
Task R - Walk
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2629 Byte
Status
Exec Time 55 ms
Memory 1920 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 1 ms 512 KB
0_01 1 ms 512 KB
0_02 1 ms 512 KB
0_03 1 ms 512 KB
0_04 2 ms 768 KB
1_00 1 ms 512 KB
1_01 1 ms 512 KB
1_02 23 ms 1920 KB
1_03 23 ms 1920 KB
1_04 26 ms 1920 KB
1_05 26 ms 1920 KB
1_06 54 ms 1920 KB
1_07 55 ms 1920 KB
1_08 54 ms 1920 KB
1_09 54 ms 1920 KB
1_10 51 ms 1920 KB
1_11 51 ms 1920 KB
1_12 45 ms 1920 KB
1_13 54 ms 1920 KB
1_14 52 ms 1920 KB
1_15 54 ms 1920 KB
1_16 55 ms 1920 KB
1_17 55 ms 1920 KB