Submission #2549216
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define je 1000000007 int su[16][16]; long long dp[16][65536]; long long mat[32][16][16]; long long sv[16][16]; long long vec[16], svec[16]; int main(){ int n, m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ scanf("%d",&su[i][j]); } } int em = (1 << m); for(int ii=0;ii<m;ii++){ for(int j=0;j<m;j++){ for(int i=0;i<em;i++){ dp[j][i] = 0; } } dp[ii][(1 << ii)] = 1; for(int i=0;i<em;i++){ for(int j=0;j<m;j++){ mat[0][ii][j] = (mat[0][ii][j] + dp[j][i]) % je; for(int k=0;k<m;k++){ if(i & (1 << k)) continue; if(!su[j][k]) continue; dp[k][i + (1 << k)] = (dp[k][i + (1 << k)] + dp[j][i]) % je; } } } } for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ printf("%lld ", mat[0][i][j]); } printf("\n"); } for(int i=1;i<=31;i++){ for(int j=0;j<m;j++){ for(int k=0;k<m;k++){ sv[j][k] = mat[i-1][j][k]; } } for(int kk=0;kk<m;kk++){ for(int ii=0;ii<m;ii++){ for(int jj=0;jj<m;jj++){ long long cal = (sv[ii][kk] * sv[kk][jj]) % je; mat[i][ii][jj] = (mat[i][ii][jj] + cal) % je; } } } } int lvl = 0; vec[0] = 1; while(n){ if(n & 1){ for(int i=0;i<m;i++){ svec[i] = vec[i]; vec[i] = 0; } for(int i=0;i<m;i++){ for(int j=0;j<m;j++){ long long cal = (mat[lvl][i][j] * svec[j]) % je; vec[j] = (vec[j] + cal) % je; } } } n /= 2; lvl++; } printf("%lld\n", vec[0]); }
Submission Info
Submission Time | |
---|---|
Task | M - 家 |
User | jihoon |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1563 Byte |
Status | WA |
Exec Time | 1112 ms |
Memory | 8448 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:14:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&n,&m); ^ ./Main.cpp:17:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&su[i][j]); ^
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 0 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | WA | 533 ms | 8448 KB |
01 | WA | 933 ms | 8448 KB |
02 | WA | 1072 ms | 8448 KB |
03 | WA | 1112 ms | 8448 KB |
04 | WA | 1051 ms | 8448 KB |
05 | WA | 935 ms | 8448 KB |
06 | WA | 454 ms | 7552 KB |
90 | WA | 1 ms | 256 KB |
91 | WA | 2 ms | 2432 KB |