czy 的后宫 (harem. cpp/c/pas)

题目描述

czy 要妥善安排他的后宫, 他想在机房摆一群妹子, 一共有 n 个位置排成一排, 每个位置可以 摆妹子也可以不摆妹子. 有些类型妹子如果摆在相邻的位置 (隔着一个空的位置不算相邻), 就不好看了. 假定每种妹子数量无限, 求摆妹子的方案数.

输入格式

输入有 m+1 行, 第一行有两个用空格隔开的正整数 n、m, m 表示妹子的种类数. 接下来的 m 行, 每行有 m 个字符 1 或 0, 若第 i 行第 j 列为 1, 则表示第 i 种妹子第 j 种妹子不能排在相邻的位置, 输入保证对称. (提示: 同一种妹子可能不能排在相邻位置).

输出格式

输出只有一个整数, 为方案数 (这个数字可能很大, 请输出方案数除以 1000000007 的余数.

样例输入

2 2
01
10

样例输出

7

样例说明

七种方案为 (空, 空)、(空, 1)、(1、空)、(2、空)、(空、2)、(1, 1)、(2, 2).

数据范围

20% 的数据,\(1 \lt n \leq 5, 0 \lt m \leq 10\).

60% 的数据,\(1 \lt n \leq 200, 0 \lt m \leq 100\).

100% 的数据,\(1 \lt n \leq 1000000000, 0 \lt m \leq 100\).

注: 此题时限 1. 5s 是因为本评测机跑太慢, 大家正常做

但写的太丑可能 T 一俩个点

Explanation

由于 \(m\) 比较小, 所以我们可以直接上矩阵快速幂.

矩阵比较不是很好建, 所以可能有点必要不在这里写矩阵构造方法.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 10010;
const int maxm = 110;
const lli modr = 1000000007;

class Matrix
{
public:
    int size;
    lli dat[maxm][maxm];
    Matrix(int n) {
        this->size = n;
        for (int i = 1; i <= this->size; i++)
            for (int j = 1; j <= this->size; j++)
                this->dat[i][j] = 0;
        return ;
    }
    Matrix(int n, int a) : Matrix(n) {
        for (int i = 1; i <= this->size; i++)
            this->dat[i][i] = a;
        return ;
    }
    Matrix(int n, lli arr[][maxm]) : Matrix(n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                this->dat[i][j] = arr[i][j];
        return ;
    }
};

Matrix operator * (Matrix a, Matrix b)
{
    if (a.size != b.size)
        throw ;
    Matrix c(a.size);
    for (int i = 1; i <= a.size; i++)
        for (int j = 1; j <= a.size; j++) {
            c.dat[i][j] = 0;
            for (int k = 1; k <= a.size; k++)
                c.dat[i][j] += (a.dat[i][k] * b.dat[k][j]) % modr;
            c.dat[i][j] %= modr;
        }
    return c;
}

Matrix operator ^ (Matrix a, lli b)
{
    Matrix c(a.size, 1);
    for (lli i = 1; i <= b; i <<= 1) {
        if ((b & i) > 0)
            c = c * a;
        a = a * a;
    }
    return c;
}

lli n;
int m;
lli arr[maxm][maxm];

int main(int argc, char** argv)
{
    scanf("%lld%d", &n, &m);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++) {
            char c = getchar();
            while (c != '0' && c != '1')
                c = getchar();
            arr[i + 1][j + 1] = c == '1' ? 0 : 1;
        }
    // There should also be a reservation for the empty spaces
    for (int i = 1; i <= m + 1; i++)
        arr[1][i] = arr[i][1] = 1;
    Matrix a(m + 1);
    Matrix b(m + 1, arr);
    for (int i = 1; i <= m + 1; i++)
        for (int j = 1; j <= m + 1; j++)
            a.dat[i][j] = 1;
    Matrix c = a * (b ^ (n - 1));
    lli sum = 0;
    for (int i = 1; i <= m + 1; i++)
        sum += c.dat[1][i];
    sum %= modr;
    printf("%lld\n", sum);
    return 0;
}