Submission #71891

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
71891	2018-08-25 19:06:02	:p (#119)	Cross on the Grid (FXCUP3_cross)	C++17	0 / 100	3 ms	480 KiB

cross

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
int main()
{
  int n; cin >> n;
  vector<array<ll, 4>> dp(n+1);
  dp[1] = {1, 0, 0, 0};
  dp[2] = {1, 0, 0, 0};
  for(int i=3; i<=n; i++)
  {
    dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]) % MOD;
    dp[i][1] = (dp[i-1][0] + dp[i-1][3] - 2*dp[i-2][1] + 2*MOD) % MOD;
    dp[i][2] = (dp[i-1][0] - dp[i-2][2] + MOD) % MOD;
    dp[i][3] = (dp[i-1][0] + dp[i-1][1] - 2*dp[i-2][3] + 2*MOD) % MOD;
    // cout << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << ' ' << endl;
  }
  cout << (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3])%MOD << endl;
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 22
• Subtask 2: 0 / 35
• Subtask 3: 0 / 43