CH Round #30 摆花[矩阵乘法]

2022-09-17 18:51:01

摆花 CH Round #30 - 清明欢乐赛

背景及描述

艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。

输入格式

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

输出格式

输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数）。

样例输入

样例输出

样例说明

七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。

数据范围与约定

20%的数据，1＜n≤5,0＜m≤10。
60%的数据，1＜n≤200,0＜m≤100。
100%的数据，1＜n≤1000000000，0＜m≤100。

正解：

这样来看这个问题，我们先定义一种新的花:不摆花，然后我们把所有种类的

花看成一个点，在不互相冲突的种类之间连一条边，其中不摆花不和所有花冲突。我们要求摆到n个位置，实际上可以认为是求这个图中长度为n的路径的条数，这样把问题转换成了经典问题，可以运用矩阵乘法求解，得 100 分

关于图中长度为n路径计数：

见图片

注意：本题必须边从0开始

//

//  main.cpp

//  ch30B

//

//  Created by Candy on 23/10/2016.

//  Copyright © 2016 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int M=,MOD=;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m;

char s[M];

struct mat{

    ll mt[M][M];

    mat(){memset(mt,,sizeof(mt));}

}g,im;

mat mult(mat &x,mat &y){

    mat t;

    for(int i=;i<=m;i++)

        for(int k=;k<=m;k++) if(x.mt[i][k])

            for(int j=;j<=m;j++)

                t.mt[i][j]=(t.mt[i][j]+x.mt[i][k]*y.mt[k][j]%MOD)%MOD;

    return t;

}

void dp(){

    for(int i=;i<=m;i++)

            im.mt[i][i]=;

    for(;n;n>>=,g=mult(g,g))

        if(n&) im=mult(im,g);

}

int main(int argc, const char * argv[]){

    //freopen("harem.in","r",stdin);

    //freopen("harem.out","w",stdout);

    n=read();m=read();

    for(int i=;i<=m;i++){

        scanf("%s",s+);

        for(int j=;j<=m;j++) g.mt[i][j]=(s[j]-'')^;

    }

    for(int i=;i<=m;i++) g.mt[i][]=g.mt[][i]=;

    dp();

    ll ans=;

    for(int i=;i<=m;i++) ans=(ans+im.mt[][i])%MOD;

    printf("%lld",ans);

}

码农公寓