AOJ2222 Alien's Counting - seica

問題概要

Alien's Counting | Aizu Online Judge
N本の指を持つエイリアンがM個の屈曲の規則を持っている。
そのエイリアンが指で数えられる数は？

みたいな感じ。
小指曲げたら薬指も曲がるねみたいな。

なんやかんややった結果、できませんでした。(´・ω・｀)ｼｮﾎﾞｰﾝ
解説ブログ見ながら解いたので、整理していきます。

考察

とりあえず、グラフの問題ですね。
有向グラフを使います。
グラフは連結とは限りません。ということで連結成分ごとに分けました。
すると、それらは独立して考えられるので、答えは各連結成分ごとに表せる数の積になりますね。これはわかりました。
また、最初のサンプルを見ていったら、強連結の所はそのうちどれか一つでも曲げられるとすべてが曲げられるので、一つとしてみるとよいことに気が付きます。
さらに、問題の条件から、一つの点から出る辺は高々1つなので、考えるべきグラフは森になると。

ここまでわかったので、あとは各連結成分が表せる数を求めればいいわけですね。
はい、できませんでした()。

DPがへたくそなんですね。
DPの考え方は(今のところ自分の中では)

ある状態と、状態遷移を考えれる。
問題を分けて考えれる。(上と同義な感じもする)

みたいなところをイメージして考えていますが、その中の状態遷移が考えられてなかったと。
まあ、今回は指を曲げる場合と曲げない場合を別に考えればうまく状態遷移を考えられたわけですね。
分岐しているところについてその点が曲げられていると仮定すると、各分岐先は独立して考えられます。

ということで、曲げた場合と曲げない場合で分ければ親の数だけ掛けてあげればいいだけになります。
子の曲げた場合の数　＝　各親の（曲げた場合の数＋曲げない場合の数）の積
子の曲げない場合の数　＝　各親の曲げない場合の数の積(結局１になるって後で気が付いた)

と、いうことで今回は

強連結成分分解してから
各連結成分についてDPで数を(指を曲げる曲げないを分けて)数えて、答えに掛けていく

という感じ。

もうちょっと状態遷移を考えれるようにしましょうね、って話でした。
どうなんだろう、この問題はここで詰まるものなんだろうか、、、。
絶対DPがまだまだな気がしている。
DPで解きたいから状態遷移を整理するぞ！みたいな気持ちが足りないのかも。
明確な目的を持ちながら問題分析していくっていうのも大事なのかもね。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

struct SCC
{
	vector<vector<int> > G;
	vector<vector<int> > rG;
	vector<int> vs;
	vector<bool> used;
	vector<int> cmp;
	int sz,newsz;
	SCC(int n):G(n),rG(n),used(n,false),cmp(n){sz = n;}
	
	void add_edge(int from,int to)
	{
		G[from].PB(to);
		rG[to].PB(from);
	}
	
	void dfs(int v)
	{
		used[v] = true;
		REP(i,G[v].size())
		{
			if(!used[G[v][i]])dfs(G[v][i]);
		}
		vs.PB(v);
	}
	
	void rdfs(int v,int k)
	{
		used[v] = false;
		cmp[v] = k;
		REP(i,rG[v].size())
		{
			if(used[rG[v][i]])rdfs(rG[v][i],k);
		}
	}
	
	int reMake()
	{

		vs.clear();
		REP(i,sz)if(!used[i])dfs(i);
		int k = 0;
		for(int i = sz-1;i >= 0;i--)
		{
			if(used[vs[i]])
			{
				rdfs(vs[i],k++);
			}
		}
		return newsz = k;
	}
	
	
	
	void makeList(vector<vector<int> > &v)
	{
		REP(i,sz)
		{
			REP(j,G[i].size())
			{
				if(cmp[i] == cmp[G[i][j]])continue;
				v[cmp[i]].PB(cmp[G[i][j]]);
			}
		}
	}

	void makeReverseList(vector<vector<int> > &v)
	{
		REP(i,sz)
		{
			REP(j,G[i].size())
			{
				if(cmp[i] == cmp[G[i][j]])continue;
				v[cmp[G[i][j]]].PB(cmp[i]);
			}
		}
	}
	
	int scc_node(int n)
	{
		return cmp[n];
	}
};


#define MOD 1000000007 

vector<vector<int> > v(1000);
vector<vector<int> > rv(1000);

bool check[10001];
ll dp[1111];

void dfs(int n)
{
	check[n] = true;
	
	if(rv[n].size() == 0)
	{
		dp[n] = 1;
		return;
	}
	
	REP(i,rv[n].size())
	{
		dfs(rv[n][i]);
	}

	ll tmpa = 1;
	ll tmpb = 1;	
	REP(i,rv[n].size())
	{
		tmpa = (tmpa * ((1+dp[rv[n][i]])%MOD))%MOD;
	}
	dp[n] = tmpa;
	
	return;
}
	

int main()
{
	int n,m;cin >> n >> m;
	
	SCC scc(n);
	REP(i,m)
	{
		int a,b;cin >> a >> b;
		a--;b--;
		scc.add_edge(a,b);
	}
	
	scc.reMake();
	scc.makeList(v);
	scc.makeReverseList(rv);
	
	
	ll ans = 1;
	REP(i,scc.newsz)
	{
		if(v[i].size() == 0 && !check[i])
		{
			dfs(i);
			ans = (ans * (1+dp[i]))%MOD;
		}
	}		
	
	cout << ans << endl;
	
	return 0;
}