TCO2015 Round1A 500. AutoGame

問題

N個の頂点があり、有向辺がN本各頂点からでている。(多重辺や自己ループもありえる。)
このとき、トークンを0〜N枚から好きな枚数を選んで、N個の頂点上に置く。ただし、同じ頂点には2個以上置けない。
今、トークンをそれぞれ同時にK回有向辺にそって動かすこと繰り返す。
トークンが動かしている途中で同じ頂点に2つ以上そろうような置き方をした場合は負け、最後まで2つ以上そろわなければ勝ちとなる。
勝ちとなるような置き方は何通り存在するか？mod 10^9+7で答える。

N<=50
K<=10^9

考え方

N次元のベクトルを用意して、有向辺の隣接行列Aを掛け合わせると、次のターンでどこに移動するか？、それぞれに置かれたトークンが同じ頂点に来る、などを確認することができる。

すべての要素を1としたベクトルを考えると、隣接行列の掛け算をすることで、同じ頂点に重なる場合は、2以上の数値になることがわかり、さらに、一度そうなると、分裂はしないので、途中で重なったものはK回後を見ても重なっていることがわかる。

行列の累乗A^Kを求めて、すべての要素が1のベクトルとかけあわせれば、K回後の状態(v')がわかるので、そこから勝つことができる置き方を求める。

0個置くとき、1個置くとき、、、とそれぞれ分けて求めようとすると、組み合わせなどが煩雑になってしまう。
(例えば、v'が(0,0,2,2)のようになった場合、3番目と4番目の2の部分にそれぞれ1個ずつまで選ぶことができる。0個の場合は、すべて選ばない組み合わせ、1個の場合は、3番目か4番目のどちらからか1つ選ぶ組み合わせ、2個の場合は、3番目から1つ、4番目から1つを選ぶ組み合わせ・・・)

しかし、見方を変えると、v'で1以上となっている数字xについて、「そこに置かない場合の1通り」と「そこに来るような頂点のうちどれかを1つ選ぶ場合のx通り」だけ取り方があり得るので、(x+1)を、それぞれの1以上となっているもので求めてすべて掛け合わせればよい。

反省

本番は組み合わせを考えるところでごちゃごちゃさせてハマってしまった・・・
「0〜N個まで任意個選んで」系は前にも解いたことがあるのに、また同じ考え方で煩雑化してしまった。
やり方を決めてしまうと先入観で別の見方ができなくなってしまう:(