問題
http://community.topcoder.com/stat?c=problem_statement&pm=13716&rd=16433
ノード数Nの有向グラフが与えられる。
エッジの数は最大Nであり、各ノードから出るエッジはひとつだけになる。
このグラフで最初に任意のノードを選んでトークンを置き、Kステップ遷移させる。
Kステップ経過後、どのトークンも重ならないような置き方の総数を求める。
解き方
法則を考えようとして複雑なコードになってしまった。
ステップ数Kは10^9であるがノード数が５０なので、シミュレーションさせて
最後の位置の重なり具合で場合の数を求めればシンプルに求められる。
コード
class Autogame {
public: int wayscnt(vector<int> a, int K) {
int n=a.size();
int p[n];
int MOD=1000000007;
FORE(i,0,n)p[i]=i;
for(int i=0;i<K && i<100;i++){
for(int j=0;j<n;j++)p[j]=a[p[j]]-1;
}
int ret=1;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n)if(p[j]==i)cnt++;
if(cnt>0)ret=(ret*1LL*(cnt+1))%MOD;
}
return ret;
}
};
public: int wayscnt(vector<int> a, int K) {
int n=a.size();
int p[n];
int MOD=1000000007;
FORE(i,0,n)p[i]=i;
for(int i=0;i<K && i<100;i++){
for(int j=0;j<n;j++)p[j]=a[p[j]]-1;
}
int ret=1;
FORE(i,0,n){
int cnt=0;
FORE(j,0,n)if(p[j]==i)cnt++;
if(cnt>0)ret=(ret*1LL*(cnt+1))%MOD;
}
return ret;
}
};