HDU 2604 Queuing_C/C++_编程开发_程序员俱乐部

class="cpp" name="code">/*
*  [题意]
*   对于只由数字1和0构成的串
*   给出长度为n的, 不含子串101且不含子串111的串的个数(mod m)
*  [解题方法]
*   设f[n]为长度是n的并且以0结尾的串的个数
*   设g[n]为长度是n的并且以1结尾的串的个数
*   则有：  1. f[n] = f[n-1](...00) + g[n-1](...10)
*          2. g[n] = f[n-2](...001) + f[n-3](...0011)
*   所以有矩阵：
*   |1 0 0 1|       |f[n-1]|        |f[n]  |
*   |1 0 0 0|   *   |f[n-2]|    =   |f[n-1]|
*   |0 1 0 0|       |f[n-3]|        |f[n-2]|
*   |0 1 1 0|       |g[n-1]|        |g[n]  |
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
#define M 4
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)

int ans[M], mod;
int init[M][M];
int ret[M][M];
int ss[M][M] = {1, 0, 0, 1,
                1, 0, 0, 0,
                0, 1, 0, 0,
                0, 1, 1, 0};

void ini(int n)
{
    ans[0] = ans[3] = 2;
    ans[1] = ans[2] = 1;
    FF(i, n) FF(j, n) init[i][j] = ss[i][j];
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i , n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    int tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + (LL)a[j]*b[i][j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for ( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int main()
{
    int n;
    while (cin >> n >> mod)
    {
        ini(M);     //初始ans矩阵为：[f2 f1 f0 g2] = [2 1 1 2]
        qmod(M, n);
        matmul(ans, ret, M);
        cout << ans[1] << endl;     //答案 = f[n] + g[n] = f[n+1]
    }
    return 0;
}

?