Submission #1690157

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long i64;

const int MOD = 1000000007;

class Matrix {
public:
  i64 num[5][5];
  int n, m;
  Matrix(int _n = 0, int _m = 0) {
    n = _n, m = _m;
    memset(num, 0, sizeof num);
  }
  inline friend Matrix operator * (const Matrix &a, const Matrix &b) {
    Matrix c = Matrix(a.n, b.m);
    for (int i = 0; i < a.n; ++i)
      for (int j = 0; j < b.m; ++j)
	for (int k = 0; k < a.m; ++k)
	  c.num[i][j] = (c.num[i][j] + a.num[i][k] * b.num[k][j]) % MOD;
    return c;
  }
} res, T1, T2, T;

Matrix fpm(Matrix x, int y) {
  Matrix res = Matrix(x.n, x.n);
  for (int i = 0; i < x.n; ++i) res.num[i][i] = 1;
  while (y) {
    if (y & 1) res = res * x;
    x = x * x;
    y >>= 1;
  }
  return res;
}

int N, M, X[100005];

int main() {
  scanf("%d%d", &N, &M);
  
  res = Matrix(1, 3), res.num[0][0] = 1;
  T1 = Matrix(3, 3), T2 = Matrix(3, 3);

  T1.num[0][0] = T1.num[1][1] = T1.num[2][2] = 1;
  T1.num[0][1] = 2, T1.num[1][2] = 1, T1.num[0][2] = 1;
  T1.num[1][0] = 1, T1.num[2][0] = 1, T1.num[0][0] += 1;
  T2 = T1, T2.num[1][0] = T2.num[2][0] = 0, T2.num[0][0] -= 1;
  
  for (int i = 1; i <= M; ++i) {
    scanf("%d", &X[i]);
    res = res * fpm(T1, X[i] - X[i - 1] - 1) * T2;
  }

  res = res * fpm(T1, N - X[M]);

  printf("%lld\n", res.num[0][2]);
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &M);
                        ^
./Main.cpp:53:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &X[i]);
                       ^

Judge Result