首页 > 代码库 > CH Round #30 摆花[矩阵乘法]
CH Round #30 摆花[矩阵乘法]
摆花 CH Round #30 - 清明欢乐赛
背景及描述
艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。
输入格式
输入有1+m行，第一行有两个用空格隔开的正整数n、m，m表示花的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位置）。
输出格式
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数）。
样例输入
2 20110
样例输出
7
样例说明
七种方案为(空，空)、（空，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=105,MOD=1000000007;typedef long long ll;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m;char s[M];struct mat{ ll mt[M][M]; mat(){memset(mt,0,sizeof(mt));}}g,im;mat mult(mat &x,mat &y){ mat t; for(int i=0;i<=m;i++) for(int k=0;k<=m;k++) if(x.mt[i][k]) for(int j=0;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=0;i<=m;i++) im.mt[i][i]=1; for(;n;n>>=1,g=mult(g,g)) if(n&1) 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=1;i<=m;i++){ scanf("%s",s+1); for(int j=1;j<=m;j++) g.mt[i][j]=(s[j]-‘0‘)^1; } for(int i=0;i<=m;i++) g.mt[i][0]=g.mt[0][i]=1; dp(); ll ans=0; for(int i=0;i<=m;i++) ans=(ans+im.mt[0][i])%MOD; printf("%lld",ans);}
CH Round #30 摆花[矩阵乘法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。