bzoj 4894: 天赋

Description

小明有许多潜在的天赋，他希望学习这些天赋来变得更强。正如许多游戏中一样，小明也有n种潜在的天赋，但有

一些天赋必须是要有前置天赋才能够学习得到的。也就是说，有一些天赋必须是要在学习了另一个天赋的条件下才

能学习的。比如，要想学会"开炮"，必须先学会"开枪"。一项天赋可能有多个前置天赋，但只需习得其中一个就可

以学习这一项天赋。上帝不想为难小明，于是小明天生就已经习得了1号天赋-----"打架"。于是小明想知道学习完

这n种天赋的方案数，答案对1,000,000,007取模。

Solution

#include<bits/stdc++.h>

using namespace std;

const int N=310,mod=1e9+7;

int a[N][N],n;char s[N];

inline void solve(){

	int ans=1;

	for(int i=2;i<=n;i++){

		for(int j=i+1;j<=n;j++)

			while(a[j][i]){

				int t=a[i][i]/a[j][i];

				for(int k=i;k<=n;k++)

					a[i][k]=(a[i][k]-1ll*a[j][k]*t)%mod,swap(a[i][k],a[j][k]);

				ans=(-ans+mod)%mod;

			}

		ans=1ll*ans*a[i][i]%mod;

	}

	if(ans<0)ans+=mod;

	printf("%d\n",ans);

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  scanf("%d",&n);

  for(int i=1;i<=n;i++){

	  scanf("%s",s+1);

	  for(int j=1;j<=n;j++){

		  a[i][j]-=s[j]-'0';

		  a[j][j]+=s[j]-'0';

	  }

  }

  solve();

  return 0;

}