Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Дополнительные олимпиадные задачи
- // Задача C. Симпатичные узоры возвращаются
- // ibelyaev: 28Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.html
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- const int MASK_BORDER = 1 << 6;
- const int MAX_DIGITS = 105;
- const int OSN = 10;
- char n[MAX_DIGITS];
- int m,p;
- int adj_mask[MASK_BORDER][MASK_BORDER];
- int MASK;
- struct BigInt {
- int amount;
- int digits[MAX_DIGITS];
- BigInt() {
- memset(digits,0,sizeof(digits));
- amount = 1;
- }
- BigInt(char *buf) {
- memset(digits,0,sizeof(digits));
- amount = strlen(buf);
- int pos = 0;
- for (int i = amount - 1; i>=0; i--)
- digits[pos++] = buf[i] - '0';
- }
- bool isZero() {
- return amount == 1 && digits[0] == 0;
- }
- bool isOdd() {
- return digits[0] & 1;
- }
- };
- BigInt operator - (const BigInt &a, const int &n) {
- BigInt res = a;
- int pos = 0;
- res.digits[pos] -= n;
- while (res.digits[pos] < 0) {
- res.digits[pos+1]--;
- res.digits[pos++] += OSN;
- }
- if (!res.digits[res.amount-1])
- res.amount--;
- return res;
- }
- BigInt operator / (const BigInt &a, const int &n) {
- BigInt res;
- int ost = 0;
- for (int i=a.amount - 1; i>=0; --i) {
- int cur = ost * OSN + a.digits[i];
- res.digits[i] = cur / n;
- ost = cur % n;
- }
- int pos = a.amount - 1;
- while (pos && !res.digits[pos])
- pos--;
- res.amount = pos + 1;
- return res;
- }
- struct matrix {
- int mas[MASK_BORDER][MASK_BORDER];
- matrix() {
- memset(mas,0,sizeof(mas));
- }
- matrix(int src[MASK_BORDER][MASK_BORDER]) {
- memcpy(mas,src,sizeof(mas));
- }
- void setE() {
- for (int i=0;i<MASK_BORDER;++i)
- mas[i][i] = 1;
- }
- void fast_mul(BigInt n) {
- matrix res, b;
- res.setE();
- b = *this;
- while (!n.isZero()) {
- if (n.isOdd()) { // &1
- res *= b;
- }
- b *= b;
- n = n / 2;
- }
- *this = res;
- }
- void operator *= (const matrix &b) {
- matrix res;
- for (int i = 0; i <= MASK; ++i) {
- for (int j = 0; j <= MASK; ++j) {
- for (int k = 0; k <= MASK; ++k) {
- res.mas[i][j] = (res.mas[i][j] + (this->mas[i][k] * b.mas[k][j]) % p ) % p;
- }
- }
- }
- *this = res;
- }
- } a;
- void input(){
- scanf("%s %d %d", &n, &m, &p);
- MASK = (1 << m) - 1;
- }
- int get_bit(int num, int bit) {
- return (num >> bit) & 1 ? 1 : 0;
- }
- void check_compatible() {
- for (int prv = 0; prv <= MASK; ++prv) {
- for (int cur = 0; cur <= MASK; ++cur) {
- bool isOK = true;
- for (int bit = 0; bit < m - 1; ++bit) {
- int sum = get_bit(prv,bit) + get_bit(prv,bit+1) +
- get_bit(cur,bit) + get_bit(cur,bit+1);
- isOK &= !(sum == 0 || sum == 4);
- }
- adj_mask[prv][cur] = isOK ? 1 : 0;
- }
- }
- }
- void solve(){
- check_compatible();
- a = matrix(adj_mask);
- a.fast_mul(BigInt(n) - 1);
- }
- void output() {
- int res = 0;
- for (int i=0; i <= MASK; ++i) {
- for (int j=0; j <= MASK; ++j)
- res = (res + a.mas[i][j]) % p;
- }
- printf("%d", res);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- output();
- return 0;
- }
Editing is locked.