题意
有 (N) 种不同的怪兽，标号为 (1) 到 (N)
每天晚上，所有的怪兽都会死去，当一只怪兽死去的时候，它会生出一只或者多只怪兽，因此怪兽的数量从来不会减少
给你一个字符数组表示每种怪兽死去的时候能生出哪些种类的怪兽
假设第 (i) 个字符串为"2 3 3"，表示第i只怪兽死的时候，1只2类型的怪兽和2只3类型的怪兽会生出来
显然，怪兽的数量可能会是无穷大的，也有些时候会变成一个定值
一开始你只有一只1类型的怪兽，你想要知道最终会有多少只怪兽，对 (1e9+7) 取模
如果有无穷多只，输出 (-1)
输入格式
第一行输入一个整数 (n) 表示怪兽的种类数 ((1≤n≤50))
接下来 (n) 行每行一个字符串由若干个数字构成
意义见题面描述
输出格式
输出一个整数
样例输入&输出
样例1
1
1
1
样例2
1
1 1
-1
样例3
3
2
3
1
1
样例4
4
1
2 4
2
2
1
样例5
7
2 2
3
4 4 4
5
6
7 7 7 7
7
24
样例6
7
2 3
5 7
2 4
5
6
4
7
5
样例7
7
2
3
6 4
3 5
2
7
2
-1
样例8
5
2
3 4
5
5
2
-1
分析
本题输入很坑，用getchar或者stringstream+string+getline。
别忘开long long。
构造一张图 (G) ，若怪物 (i) 能繁殖出一只怪物 (j) ，则连边 (<i,j>) （有向边）
1. dfs判环，dfs计算答案 ( ext{Time Limit Exceeded})
若存在一个在环上的点，它的出度大于1，那么肯定会无限循环。
用邻接矩阵存图，因为可能存在很多重边。
#include<cstdio>
#include<cstdlib>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#define maxn 52
#define maxm 2502
#define mod 1000000007
using namespace std;
char ch;
int read(int& x){
x=0;
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
while(ch==' ')ch=getchar();
if(ch==EOF){
return 0;
}
if(ch=='
'){
ch=getchar();
return 0;
}
return 1;
}
int n,g[maxn][maxn],st[maxn],top;
bool oncyc[maxn],inst[maxn];
void getcyc(int u){
st[++top]=u;
inst[u]=1;
int count=0;
for(int v=1;v<=n;v++){
if(!g[u][v])continue;
count+=g[u][v];
if(!inst[v]){
getcyc(v);
}
else{
int t;
for(t=top;st[t]!=v;t--);
for(int i=t;i<=top;i++){
oncyc[st[i]]=1;
}
}
if(oncyc[u]&&count>1){
printf("-1
");
exit(0);
}
}
top--;
inst[u]=0;
}
long long DFS(int u){
long long ret=0;
for(int v=1;v<=n;v++){
if(!g[u][v])continue;
if(oncyc[v]){
ret=(ret+g[u][v])%mod;
continue;
}
ret=(ret+DFS(v)*g[u][v]%mod)%mod;
}
return ret;
}
int main(){
while(ch<'0'||ch>'9')ch=getchar();
read(n);
for(int u=1;u<=n;u++){
int v;
bool tmp;
while(1){
tmp=read(v);
g[u][v]++;
if(!tmp)break;
}
}
getcyc(1);
printf("%lld
",DFS(1));
return 0;
}
2. 矩阵快速幂
我们定义矩阵$$S=[1,0,0,...,0]$$
(S) 长为 (1) ，宽为 (n)
再定义矩阵 (A) 为 (G) 的邻接矩阵
我们发现，怪兽每繁殖一次，相当于做一次 (S=S* A) 的运算
我们用矩阵快速幂，让 (S) 分别乘 (1e8) 和 (2e8) 次得到矩阵 (R) 和 (T) ，由于结果很大，所以要取模，多取几个模数，比较 (R) 和 (T) 中元素之和是否相等。由于最后输出的答案需要取模 (1e9+7) ，所以把 (1e9+7) 放在最后取模。
Code
#include<cstdio>
#pragma GCC optimize(2)
#define maxn 52
using namespace std;
long long mod;
long long Plus(long long a,long long b){
long long ret=a+b;
return ret>=mod?ret-mod:ret;
}
long long mul(long long a,long long b){
return a*b%mod;
}
struct matrix{
long long a[maxn][maxn];
int n,m;
matrix& operator =(const matrix& M){
n=M.n,m=M.m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=M.a[i][j];
}
}
}
void init(int _n,int _m){
n=_n,m=_m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)a[i][j]=0;
a[i][i]=1;
}
}
void init0(int _n=0,int _m=0){
n=_n,m=_m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=0;
}
}
}
void output()const{
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%lld ",a[i][j]);
}
putchar('
');
}
}
};
const matrix mul(const matrix& a,const matrix& b){
matrix ans;
ans.init0(a.n,b.m);
if(a.m!=b.n)return ans;
for(int i=1;i<=a.n;i++){
for(int j=1;j<=b.m;j++){
ans.a[i][j]=0;
for(int k=1;k<=a.m;k++){
ans.a[i][j]=Plus(ans.a[i][j],mul(a.a[i][k],b.a[k][j]));
}
}
}
return ans;
}
matrix qpow(matrix a,long long b){
matrix ans;
ans.init(a.n,a.m);
while(b){
if(b&1)ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
};
matrix s,t,g;
int n;
namespace INIT{
char ch;
int read(int& x){
x=0;
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
while(ch==' ')ch=getchar();
if(ch==EOF){
return 0;
}
if(ch=='
'){
ch=getchar();
return 0;
}
return 1;
}
void init(){
while(ch<'0'||ch>'9')ch=getchar();
read(n);
g.n=g.m=n;
for(int u=1;u<=n;u++){
int v;
bool tmp;
while(1){
tmp=read(v);
g.a[u][v]++;
if(!tmp)break;
}
}
}
}
long long MOD[5]={0,19260817,1000000009,998244353,1000000007};
int main(){
INIT::init();
long long ans1,ans2;
for(int j=1;j<=4;j++){
mod=MOD[j];
s.init(1,n);
s=mul(s,qpow(g,100000000));
t.init(1,n);
t=mul(t,qpow(g,200000000));
ans1=ans2=0;
for(int i=1;i<=n;i++)ans1=Plus(ans1,s.a[1][i]),ans2=Plus(ans2,t.a[1][i]);
if(ans1!=ans2){
puts("-1");
return 0;
}
}
printf("%lld
",ans1);
return 0;
}
3. 强连通分量，缩点
Unknown
Code