Guest User

Untitled

a guest
Feb 18th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include <cstring>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <sstream>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <complex>
  17. #include <list>
  18. #include <climits>
  19. #include <cctype>
  20. #include <bitset>
  21. using namespace std;
  22. int N, k, mask, next;
  23. long long dp[31][1 << 3];
  24. void Search(int i){
  25. if(i == 3){
  26. dp[k + 1][next] += dp[k][mask];
  27. return;
  28. }
  29. if(mask & (1 << i)){
  30. Search(i + 1);
  31. return;
  32. }
  33. if(i + 1 < 3 && !(mask & (1 << (i + 1))))
  34. Search(i + 2);
  35. if(k + 1 < N){
  36. next ^= (1 << i);
  37. Search(i + 1);
  38. next ^= (1 << i);
  39. }
  40.  
  41. }
  42. int main(){
  43. while(scanf("%d", &N) != EOF && N != -1){
  44. memset(dp, 0, sizeof dp);
  45. dp[0][0] = 1;
  46. for(k = 0; k < N; k++)
  47. for(mask = 0; mask < (1 << 3); mask++){
  48. next = 0;
  49. Search(0);
  50. }
  51. printf("%lld\n", dp[N][0]);
  52. }
  53. return 0;
  54. }
Add Comment
Please, Sign In to add comment