v 0. Pasted by slipstak2 as cpp at 2011-10-28 20:54:53 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Дополнительные олимпиадные задачи
  3. // Задача C. Симпатичные узоры возвращаются
  4. // ibelyaev: 28Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. const int MASK_BORDER = 1 << 6;
  25. const int MAX_DIGITS = 105;
  26. const int OSN = 10;
  27.  
  28. char n[MAX_DIGITS];
  29. int m,p;
  30. int adj_mask[MASK_BORDER][MASK_BORDER];
  31. int MASK;
  32.  
  33. struct BigInt {
  34.     int amount;
  35.     int digits[MAX_DIGITS];
  36.     BigInt() {
  37.         memset(digits,0,sizeof(digits));
  38.         amount = 1;
  39.     }
  40.     BigInt(char *buf) {
  41.         memset(digits,0,sizeof(digits));
  42.         amount = strlen(buf);
  43.         int pos = 0;
  44.         for (int i = amount - 1; i>=0; i--)
  45.             digits[pos++] = buf[i] - '0';
  46.     }
  47.     bool isZero() {
  48.         return amount == 1 && digits[0] == 0;
  49.     }
  50.     bool isOdd() {
  51.         return digits[0] & 1;
  52.     }
  53. };
  54. BigInt operator - (const BigInt &a, const int &n) {
  55.     BigInt res = a;
  56.     int pos = 0;
  57.     res.digits[pos] -= n;
  58.     while (res.digits[pos] < 0) {
  59.         res.digits[pos+1]--;
  60.         res.digits[pos++] += OSN;
  61.     }
  62.     if (!res.digits[res.amount-1])
  63.         res.amount--;
  64.     return res;
  65. }
  66. BigInt operator / (const BigInt &a, const int &n) {
  67.     BigInt res;
  68.     int ost = 0;
  69.     for (int i=a.amount - 1; i>=0; --i) {
  70.         int cur = ost * OSN + a.digits[i];
  71.         res.digits[i] = cur / n;
  72.         ost = cur % n;
  73.     }
  74.     int pos = a.amount - 1;
  75.     while (pos && !res.digits[pos])
  76.         pos--;
  77.     res.amount = pos + 1;
  78.     return res;
  79. }
  80.  
  81. struct matrix {
  82.     int mas[MASK_BORDER][MASK_BORDER];
  83.     matrix() {
  84.         memset(mas,0,sizeof(mas));
  85.     }
  86.     matrix(int src[MASK_BORDER][MASK_BORDER]) {
  87.         memcpy(mas,src,sizeof(mas));
  88.     }
  89.     void setE() {
  90.         for (int i=0;i<MASK_BORDER;++i)
  91.             mas[i][i] = 1;
  92.     }
  93.     void fast_mul(BigInt n) {
  94.         matrix res, b;
  95.         res.setE();
  96.         b = *this;
  97.         while (!n.isZero()) {
  98.             if (n.isOdd()) { // &1
  99.                 res *= b;
  100.             }
  101.             b *= b;
  102.             n = n / 2;
  103.         }
  104.         *this = res;
  105.     }
  106.     void operator *= (const matrix &b) {
  107.         matrix res;
  108.         for (int i = 0; i <= MASK; ++i) {
  109.             for (int j = 0; j <= MASK; ++j) {
  110.                 for (int k = 0; k <= MASK; ++k) {
  111.                     res.mas[i][j] = (res.mas[i][j] + (this->mas[i][k] * b.mas[k][j]) % p ) % p;
  112.                 }
  113.             }
  114.         }
  115.         *this = res;
  116.     }
  117. } a;
  118. void input(){
  119.     scanf("%s %d %d", &n, &m, &p);
  120.     MASK = (1 << m) - 1;
  121. }
  122. int get_bit(int num, int bit) {
  123.     return (num >> bit) & 1 ? 1 : 0;
  124. }
  125. void check_compatible() {
  126.     for (int prv = 0; prv <= MASK; ++prv) {
  127.         for (int cur = 0; cur <= MASK; ++cur) {
  128.             bool isOK = true;
  129.             for (int bit = 0; bit < m - 1; ++bit) {
  130.                 int sum = get_bit(prv,bit) + get_bit(prv,bit+1) +
  131.                           get_bit(cur,bit) + get_bit(cur,bit+1);
  132.                 isOK &= !(sum == 0 || sum == 4);
  133.             }
  134.             adj_mask[prv][cur] = isOK ? 1 : 0;
  135.         }
  136.     }
  137. }
  138. void solve(){
  139.     check_compatible();
  140.     a = matrix(adj_mask);
  141.     a.fast_mul(BigInt(n) - 1);
  142. }
  143. void output() {
  144.     int res = 0;
  145.     for (int i=0; i <= MASK; ++i) {
  146.         for (int j=0; j <= MASK; ++j)
  147.             res = (res + a.mas[i][j]) % p;
  148.     }
  149.     printf("%d", res);
  150. }
  151. int main()
  152. {
  153.     freopen("input.txt","r",stdin);
  154.     freopen("output.txt","w",stdout);
  155.  
  156.     input();
  157.     solve();
  158.     output();
  159.  
  160.     return 0;
  161. }


Editing is locked.