Submission #1242709
Source Code Expand
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif
using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<Vl> VVl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
#define BASE (1000000000 + 7)
#define MAX_N (1000000000)
#define MAX_M (100000)
int N, M;
int X[MAX_M + 1];
Vl A{1, 3, 1};
VVl P{
{2, 1, 0},
{3, 1, 2},
{1, 0, 1}},
Q{{1, 1, 0},
{0, 1, 2},
{0, 0, 1}},
R(3, Vl(3));
void mat_print(VVl &a) {
#ifdef DEBUG
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[0].size(); j++) {
debug_printf("%lld ", a[i][j]);
}
debug_printf("\n");
}
#endif
}
void mat_prod(VVl &a, VVl b, VVl c) {
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[0].size(); j++) {
a[i][j] = 0;
for (int k = 0; k < b[0].size(); k++) a[i][j] = (a[i][j] + b[i][k] * c[k][j]) % BASE;
}
}
}
void mat_pow(VVl &a, VVl b, ll n) {
if (n == 0) {
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < a[0].size(); j++) a[i][j] = (i == j)? 1: 0;
} else {
mat_pow(a, b, n / 2);
mat_prod(a, a, a);
if (n % 2 == 1) mat_prod(a, a, b);
}
}
void solve() {
mat_pow(R, P, X[0] - 1);
for (int i = 1; i <= M; i++) {
VVl s(3, Vl(3));
mat_prod(R, R, Q);
mat_pow(s, P, X[i] - X[i - 1] - 1);
mat_prod(R, R, s);
}
ll ans = 0;
for (int i = 0; i < 3; i++) ans = (ans + R[0][i] * A[i]) % BASE;
printf("%lld\n", ans);
}
int main() {
cin >> N >> M;
for (int i = 0; i < M; i++) cin >> X[i];
X[M] = N;
solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Placing Squares |
User |
abyataro |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
2128 Byte |
Status |
AC |
Exec Time |
1145 ms |
Memory |
640 KB |
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 |
363 ms |
384 KB |
subtask_1_02.txt |
AC |
91 ms |
256 KB |
subtask_1_03.txt |
AC |
38 ms |
384 KB |
subtask_1_04.txt |
AC |
98 ms |
512 KB |
subtask_1_05.txt |
AC |
1144 ms |
640 KB |
subtask_1_06.txt |
AC |
1145 ms |
640 KB |
subtask_1_07.txt |
AC |
161 ms |
640 KB |
subtask_1_08.txt |
AC |
164 ms |
640 KB |
subtask_1_09.txt |
AC |
14 ms |
256 KB |
subtask_1_10.txt |
AC |
10 ms |
256 KB |
subtask_1_11.txt |
AC |
3 ms |
256 KB |
subtask_1_12.txt |
AC |
2 ms |
256 KB |
subtask_1_13.txt |
AC |
4 ms |
256 KB |
subtask_1_14.txt |
AC |
8 ms |
256 KB |
subtask_1_15.txt |
AC |
2 ms |
256 KB |
subtask_1_16.txt |
AC |
3 ms |
256 KB |
subtask_1_17.txt |
AC |
51 ms |
384 KB |
subtask_1_18.txt |
AC |
117 ms |
512 KB |
subtask_1_19.txt |
AC |
1 ms |
256 KB |
subtask_1_20.txt |
AC |
151 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 |