Submission #4330480
Source Code Expand
#include <bits/stdc++.h>
#define int long long int
#define MOD(x) ((x % MOD_N) + MOD_N) % MOD_N
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,v) for(auto i=v.begin();i!=v.end();++i)
#define REACH(i,v) for(auto i=v.rbegin();i!=v.rend();++i)
#define LB(c,x) distance((c).begin(),lower_bound(ALL(c),x))
#define UB(c,x) distance((c).begin(),upper_bound(ALL(c),x))
#define COUNT(c,x) (lower_bound(ALL(c),x)-upper_bound(ALL(c),x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl;
#define NL cerr<<endl;
using namespace std;
template<typename T,typename U> using P=pair<T,U>;
template<typename T> using V=vector<T>;
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T sum(vector<T>&v){return accumulate(ALL(v),T());}
template<typename T>T sum(vector<T>&v,int a,int b){return accumulate(v.begin()+a,v.begin()+b,T());}
template<typename T>T max(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T min(vector<T>&v){return *max_element(ALL(v));}
template<typename T>T max_index(vector<T>&v){return distance((v).begin(),max_element(ALL(v)));}
template<typename T>T min_index(vector<T>&v){return distance((v).begin(),min_element(ALL(v)));}
struct edge { int to, cost; };
template<typename T>auto&operator<<(ostream&s,const vector<T>&v){s<<"[";bool a=1;for(auto e:v){s<<(a?"":" ")<<e;a=0;}s<<"]";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const pair<T,U>&p){s<<"("<<p.first<<","<<p.second<<")";return s;}
template<typename T>auto&operator<<(ostream&s,const set<T>&st){s<<"{";bool a=1;for(auto e:st){s<<(a?"":" ")<<e;a=0;}s<<"}";return s;}
template<typename T,typename U>auto&operator<<(ostream&s,const map<T,U>&m){s<<"{";bool a=1;for(auto e:m){s<<(a?"":" ")<<e.first<<":"<<e.second;a=0;}s<<"}";return s;}
const int INF = 1e18;
const int MOD_N = 1e9+7;
template<typename T> class Matrix
{
private:
vector<vector<T>> val;
int m, n;
public:
Matrix(int a=0, int b=0) : m(a), n(b) {
val.resize(m, vector<T>(n));
}
Matrix(const vector<vector<T>>& vec) : m(vec.size()), n(vec[0].size()) {
val.resize(m, vector<T>(n));
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
val[i][j] = vec[i][j];
}
// ~Matrix() {
// vector<vector<T>>().swap(val);
// }
Matrix& operator=(const Matrix& mat) {
try { if (m != mat.m || n != mat.n) throw "Matrix can't be substituted"; }
catch (const char* e) { cerr << e << endl; }
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
val[i][j] = mat.val[i][j];
return *this;
}
T operator()(int i, int j) {
try { if (i < 0 || m <= i || j < 0 || n <= j) throw "Bad access"; }
catch (const char* e) { cerr << e << endl; }
return val[i][j];
}
const Matrix operator+(const Matrix& mat) const {
try { if (m != mat.m || n != mat.n) throw "Matrix can't be added"; }
catch (const char* e) { cerr << e << endl; }
Matrix tmp(m, n);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
tmp.val[i][j] = val[i][j] + mat.val[i][j];
return tmp;
}
const Matrix operator-(const Matrix& mat) const {
try { if (m != mat.m || n != mat.n) throw "Matrix can't be subtracted"; }
catch (const char* e) { cerr << e << endl; }
Matrix tmp(m, n);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
tmp.val[i][j] = val[i][j] - mat.val[i][j];
return tmp;
}
const Matrix operator*(const Matrix& mat) const {
try { if (n != mat.m) throw "Matrix can't be producted"; }
catch (const char* e) { cerr << e << endl; }
Matrix tmp(m, mat.n);
for (int i = 0; i < m; i++) for (int j = 0; j < mat.n; j++) for (int k = 0; k < n; k++)
// tmp.val[i][j] += val[i][k]*mat.val[k][j];
tmp.val[i][j] = MOD(tmp.val[i][j] + val[i][k]*mat.val[k][j]);
return tmp;
}
Matrix& operator+=(const Matrix& mat) {
try { if (m != mat.m || n != mat.n) throw "Matrix can't be added"; }
catch (const char* e) { cerr << e << endl; }
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
val[i][j] += mat.val[i][j];
return *this;
}
Matrix& operator-=(const Matrix& mat) {
try { if (m != mat.m || n != mat.n) throw "Matrix can't be subtracted"; }
catch (const char* e) { cerr << e << endl; }
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
val[i][j] -= mat.val[i][j];
return *this;
}
Matrix operator*=(const Matrix& mat) {
try { if (n != mat.m) throw "Matrix can't be producted"; }
catch (const char* e) { cerr << e << endl; }
Matrix tmp(m, mat.n);
for (int i = 0; i < m; i++) for (int j = 0; j < mat.n; j++) for (int k = 0; k < n; k++)
// tmp.val[i][j] += val[i][k]*mat.val[k][j];
tmp.val[i][j] = MOD(tmp.val[i][j] + val[i][k]*mat.val[k][j]);
n = mat.n;
val.resize(m, vector<T>(n));
*this = tmp;
return *this;
}
Matrix transpose() const {
Matrix tmp(n, m);
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
tmp.val[j][i] = val[i][j];
return tmp;
}
Matrix gaussElimination() const {
Matrix<T> A(val);
int col = 0;
for (int i = 0; i < m; i++) {
int pivot = i;
while (true) {
for (int j = i+1; j < m; j++) if (abs(A.val[j][col]) > abs(A.val[pivot][col])) pivot = j;
if (A.val[pivot][col] == 0) {
col++;
if (col == n) return A;
} else break;
}
swap(A.val[i], A.val[pivot]);
for (int j = i+1; j < m; j++) {
T ratio = A.val[j][col] / A.val[i][col];
for (int k = col; k < n; k++) A.val[j][k] -= A.val[i][k] * ratio;
}
col++;
}
return A;
}
int rank() const {
Matrix A = gaussElimination();
int j = 0;
for (int i = 0; i < m; i++) {
while (A.val[i][j] == 0) {
j++; if (j == n) return i;
}
}
return m;
}
ostream& info(ostream& s) const {
s << endl << "[";
for (int i = 0; i < m; i++) {
s << "[";
for (int j = 0; j < n; j++) {
s << val[i][j];
if (j < n-1) s << " ";
}
s << "]"; if (i < m-1) s << endl;
}
s << "]";
return s;
}
};
template<typename T> ostream& operator<<(ostream& s, const Matrix<T>& mat) {
mat.info(s);
return s;
}
template<typename T>
Matrix<T> power(Matrix<T> A, int n, int h) {
V<V<int>> E(n, V<int>(n));
REP(i, n) {
E[i][i] = 1;
}
Matrix<int> res(E);
while (h > 0) {
if ((h & 1) == 1) res *= A;
A *= A;
h >>= 1;
}
return res;
}
signed main()
{
int H, R; cin >> H >> R;
V<V<int>> g(R, V<int>(R));
REP(i, R) {
REP(j, R) {
cin >> g[i][j];
}
}
V<V<V<int>>> dp(R, V<V<int>>(1<<R, V<int>(R)));
REP(k, R) {
dp[k][1<<k][k] = 1;
REP(S, 1<<R) {
REP(i, R) {
if (!(S >> i & 1)) continue;
REP(j, R) {
if (!(S >> j & 1)) continue;
// dp[k][S][i] += dp[k][S & ~(1<<i)][j] * g[j][i];
dp[k][S][i] = MOD(dp[k][S][i] + dp[k][S & ~(1<<i)][j] * g[j][i]);
}
}
}
}
V<V<int>> num(R, V<int>(R));
REP(i, R) {
REP(j, R) {
REP(S, 1<<R) {
// num[i][j] += dp[i][S][j];
num[i][j] = MOD(num[i][j] + dp[i][S][j]);
}
}
}
Matrix<int> A(num);
A = power(A, R, H);
cout << A(0,0) << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
M - 家 |
User |
habara_k |
Language |
C++14 (GCC 5.4.1) |
Score |
5 |
Code Size |
8940 Byte |
Status |
AC |
Exec Time |
908 ms |
Memory |
183040 KB |
Judge Result
Set Name |
All |
Score / Max Score |
5 / 5 |
Status |
|
Set Name |
Test Cases |
All |
00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name |
Status |
Exec Time |
Memory |
00 |
AC |
902 ms |
183040 KB |
01 |
AC |
904 ms |
183040 KB |
02 |
AC |
903 ms |
183040 KB |
03 |
AC |
903 ms |
183040 KB |
04 |
AC |
908 ms |
183040 KB |
05 |
AC |
908 ms |
183040 KB |
06 |
AC |
374 ms |
79356 KB |
90 |
AC |
1 ms |
256 KB |
91 |
AC |
1 ms |
256 KB |