Submission #1692430
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b) for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
const int N = 100000;
const int mo = 1e9 + 7;
const int oo = 0x3f3f3f3f;
template<typename T> T read() {
T n(0), f(1);
char ch = getchar();
for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48;
return n * f;
}
int n, m;
int p[N + 5];
struct Matrix {
int ret[4][4];
Matrix(const bool& t = 0) {
memset(ret, 0, sizeof ret);
if(t) ret[0][0] = ret[1][1] = ret[2][2] = ret[3][3] = 1;
}
} A, B;
Matrix operator * (const Matrix& a, const Matrix& b) {
Matrix c;
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
for(int k = 0; k < 4; ++k) if(a.ret[i][k] && b.ret[k][j])
c.ret[i][j] = (c.ret[i][j] + 1ll * a.ret[i][k] * b.ret[k][j]) % mo;
return c;
}
Matrix operator ^ (const Matrix& a, int exp) {
Matrix res = 1, base = a;
for(; exp > 0; exp >>= 1) {
if(exp & 1)
res = res * base;
base = base * base;
}
return res;
}
int main() {
#ifdef Wearry
freopen("data.txt", "r", stdin);
freopen("ans.txt", "w", stdout);
#endif
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
scanf("%d", p + i);
}
if(n == 1) return puts("1"), 0;
A.ret[0][0] = 1;
A.ret[1][0] = 2;
A.ret[2][0] = 3;
A.ret[3][0] = 1;
B.ret[0][0] = 1; B.ret[0][1] = 1; B.ret[0][2] = 0; B.ret[0][3] = 2;
B.ret[1][0] = 1; B.ret[1][1] = 2; B.ret[1][2] = 0; B.ret[1][3] = 2;
B.ret[2][0] = 1; B.ret[2][1] = 2; B.ret[2][2] = 1; B.ret[2][3] = 2;
B.ret[3][0] = 0; B.ret[3][1] = 0; B.ret[3][2] = 1; B.ret[3][3] = 0;
int cur = 1;
for(int i = 0; i < m; ++i) {
A = (B ^ (p[i] - cur)) * A;
cur = p[i];
A.ret[1][0] -= A.ret[0][0];
A.ret[2][0] -= A.ret[0][0];
}
A = (B ^ (n - cur)) * A;
printf("%d\n", (A.ret[0][0] + mo) % mo);
return 0;
}
Submission Info
Submission Time
2017-10-18 20:41:21+0900
Task
E - Placing Squares
User
Wearry
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
2463 Byte
Status
AC
Exec Time
419 ms
Memory
640 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:65:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:67:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", p + i);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1600 / 1600
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt
Case Name
Status
Exec Time
Memory
sample_01.txt
AC
1 ms
256 KB
sample_02.txt
AC
1 ms
256 KB
sample_03.txt
AC
1 ms
256 KB
sample_04.txt
AC
1 ms
256 KB
subtask_1_01.txt
AC
133 ms
384 KB
subtask_1_02.txt
AC
35 ms
256 KB
subtask_1_03.txt
AC
12 ms
384 KB
subtask_1_04.txt
AC
30 ms
512 KB
subtask_1_05.txt
AC
419 ms
640 KB
subtask_1_06.txt
AC
419 ms
640 KB
subtask_1_07.txt
AC
48 ms
640 KB
subtask_1_08.txt
AC
48 ms
640 KB
subtask_1_09.txt
AC
6 ms
256 KB
subtask_1_10.txt
AC
5 ms
256 KB
subtask_1_11.txt
AC
2 ms
256 KB
subtask_1_12.txt
AC
2 ms
256 KB
subtask_1_13.txt
AC
3 ms
256 KB
subtask_1_14.txt
AC
4 ms
256 KB
subtask_1_15.txt
AC
2 ms
256 KB
subtask_1_16.txt
AC
2 ms
256 KB
subtask_1_17.txt
AC
17 ms
384 KB
subtask_1_18.txt
AC
36 ms
512 KB
subtask_1_19.txt
AC
1 ms
256 KB
subtask_1_20.txt
AC
44 ms
640 KB
subtask_1_21.txt
AC
1 ms
256 KB
subtask_1_22.txt
AC
1 ms
256 KB
subtask_1_23.txt
AC
1 ms
256 KB
subtask_1_24.txt
AC
1 ms
256 KB
subtask_1_25.txt
AC
1 ms
256 KB
subtask_1_26.txt
AC
1 ms
256 KB
subtask_1_27.txt
AC
1 ms
256 KB
subtask_1_28.txt
AC
1 ms
256 KB
subtask_1_29.txt
AC
1 ms
256 KB
subtask_1_30.txt
AC
1 ms
256 KB