Submission #1692427

---

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]);
    return 0;
}

Submission Info

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