# CMU: Tiling

Dec 3rd, 2021
594
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /// Tiling 1
2. #include <bits/stdc++.h>
3.
4. using namespace std;
5.
6. int main(){
7.
8.     int n, m;
9.     cin >> n >> m;
10.
11.     long long dp[n + 1];
12.     dp[0] = 1;
13.     for(int i=1;i<=n;i++){
14.         if(i - m < 0) dp[i] = dp[i - 1];
15.         else dp[i] = dp[i - 1] + dp[i - m];
16.     }
17.
18.     cout << dp[n];
19.
20.     return 0;
21. }
22.
23. /// Tiling 2
24. #include <bits/stdc++.h>
25.
26. using namespace std;
27. const int N = 30;
28. int three[N + 10], two[N + 10];
29.
30. int main(){
31.
32.     three[0] = 1;
33.     three[1] = 0;
34.     two[0] = 0;
35.     two[1] = 1;
36.
37.     for(int i=2;i<=N;i++){
38.         three[i] = three[i - 2] + two[i - 1] + two[i - 1];
39.         ///        full area      top          bottom
40.
41.         two[i] = three[i - 1] + two[i - 2];
42.     }
43.
44.     int q;
45.     scanf("%d", &q);
46.
47.     while(q--){
48.         int n;
49.         scanf("%d", &n);
50.         printf("%d\n", three[n]);
51.     }
52.
53.     return 0;
54. }
55.
56. /// Tiling 3
57. #include <bits/stdc++.h>
58.
59. using namespace std;
60. using lli = long long;
61. const lli mod = 1e9 + 7;
62. const int N = 1e3 + 10;
63. lli full[N], top[N], bottom[N];
64.
65. int main(){
66.
67.     int n;
68.     scanf("%d", &n);
69.
70.     full[1] = 1;
71.     full[2] = 2;
72.     top[2] = 1;
73.     bottom[2] = 1;
74.
75.     for(int i=3;i<=n;i++){
76.         full[i] = (full[i - 1] + full[i - 2] + top[i - 1] + bottom[i - 1]) % mod;
77.         top[i] = (full[i - 2] + bottom[i - 1]) % mod;
78.         bottom[i] = (full[i - 2] + top[i - 1]) % mod;
79.     }
80.
81.     printf("%lld", full[n]);
82.
83.     return 0;
84. }