Submission #1481444
Source Code Expand
#include <bits/stdc++.h>
const int N = 1e9 + 100;
const int M = 1e5 + 100;
const int MOD = 1e9 + 7;
int n, m;
int a[M];
struct Matrix {
int x[3][3];
void reset() {
std::memset(x, 0, sizeof(x));
}
void setI() {
std::memset(x, 0, sizeof(x));
x[0][0] = x[1][1] = x[2][2] = 1;
}
void add(int r, int c, int delta) {
x[r][c] += delta;
}
friend Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix result;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
result.x[i][j] = 0;
for (int k = 0; k < 3; k++) {
result.x[i][j] += (long long)a.x[i][k] * b.x[k][j] % MOD;
result.x[i][j] %= MOD;
}
}
}
return result;
}
friend Matrix operator ^ (Matrix a, int b) {
Matrix result;
result.reset();
for (int i = 0; i < 3; i++) {
result.x[i][i] = 1;
}
for ( ; b; b >>= 1) {
if (b & 1) {
result = result * a;
}
a = a * a;
}
return result;
}
};
void init() {
std::cin >> n >> m;
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
}
void work() {
static Matrix trans[2];
static Matrix mat;
mat.setI();
trans[0].reset();
trans[1].reset();
// 0
// empty
trans[0].add(0, 0, 1);
trans[0].add(1, 1, 1);
trans[0].add(2, 2, 1);
// cut
trans[0].add(2, 0, 1);
// cut - ball
trans[0].add(2, 1, 2);
// cut - ball - ball
trans[0].add(2, 2, 1);
// ball
trans[0].add(0, 1, 2);
trans[0].add(1, 2, 1);
// ball - ball
trans[0].add(0, 2, 1);
// 1
// empty
trans[1].add(0, 0, 1);
trans[1].add(1, 1, 1);
trans[1].add(2, 2, 1);
// ball
trans[1].add(0, 1, 2);
trans[1].add(1, 2, 1);
// ball - ball
trans[1].add(0, 2, 1);
int cur = 1;
for (int i = 1; i <= m; i++) {
mat = mat * (trans[0] ^ (a[i] - cur));
mat = mat * trans[1];
cur = a[i] + 1;
}
mat = mat * (trans[0] ^ (n - cur));
long long answer = 1LL * mat.x[0][2] + 2LL * mat.x[1][2] + 1LL * mat.x[2][2];
std::cout << answer % MOD << std::endl;
}
int main() {
init();
work();
return 0;
}
Submission Info
Submission Time
2017-08-04 20:53:12+0900
Task
E - Placing Squares
User
SpoiledInnocence
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
2085 Byte
Status
AC
Exec Time
240 ms
Memory
640 KB
Compile Error
./Main.cpp: In function ‘void init()’:
./Main.cpp:59:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[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
77 ms
384 KB
subtask_1_02.txt
AC
20 ms
256 KB
subtask_1_03.txt
AC
9 ms
384 KB
subtask_1_04.txt
AC
21 ms
512 KB
subtask_1_05.txt
AC
240 ms
640 KB
subtask_1_06.txt
AC
239 ms
640 KB
subtask_1_07.txt
AC
34 ms
640 KB
subtask_1_08.txt
AC
34 ms
640 KB
subtask_1_09.txt
AC
4 ms
256 KB
subtask_1_10.txt
AC
3 ms
256 KB
subtask_1_11.txt
AC
2 ms
256 KB
subtask_1_12.txt
AC
1 ms
256 KB
subtask_1_13.txt
AC
2 ms
256 KB
subtask_1_14.txt
AC
2 ms
256 KB
subtask_1_15.txt
AC
1 ms
256 KB
subtask_1_16.txt
AC
1 ms
256 KB
subtask_1_17.txt
AC
11 ms
384 KB
subtask_1_18.txt
AC
25 ms
512 KB
subtask_1_19.txt
AC
1 ms
256 KB
subtask_1_20.txt
AC
31 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