Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // https://www.geeksforgeeks.org/tiling-with-dominoes/
- void solve()
- {
- int n; cin >> n;
- int dp[n][3];
- f(i, 0, n - 1) {
- if(i == 0) {
- dp[i][0] = 0;
- dp[i][1] = 0;
- dp[i][2] = 0;
- }
- else if(i == 1) {
- dp[i][0] = 1;
- dp[i][1] = 1;
- dp[i][2] = 1;
- }
- else {
- dp[i][0] = 3 * dp[i - 2][0] + dp[i - 2][2];
- dp[i][1] = 3 * dp[i - 2][0] + dp[i - 2][2];
- dp[i][2] = 2 * dp[i - 2][0] + dp[i - 2][2];
- }
- }
- cout << dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2] << endl;
- }
- int main()
- {
- fastio();
- int _t; cin >> _t; while(_t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
