Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2012-03-27

Codeforces Div1 114 (167) E

02:48

問題:

k source, k sink のDAG が与えられる.

各ソースからシンクに向かう点素なk本のパスであって,それが偶置換をなすものについて+1

奇置換をなすものについて,-1 を寄与させる.

すべての可能なパスの組み合わせについて,この寄与の合計をmod p で求めよ.

  • n <= 600
  • m <= 10^5
  • p is prime, p <= 10^9 + 7

解法:

偶置換,奇置換という言い方が出来れば,行列式を思い浮かべる.

行列A の行列式として表せないか. と考える.

A_i,j : source i -> sink j のパスの総数とする.(これはトポロジカルソートした後にDPで,O(km)で求めた)

すると, 置換sに対して, A_i,s(i) の積が,点素なパスの数になっているだろうか.

というと,そんなことはなくて,点を共有するものを含んでいるけど,そういうやつは,

共有する点で行き方を変えたやつと,符号が変わってキャンセルされる.*1

結局,点素なものだけが寄与として残る.

行列式の計算で逆元を求めるので,素数という条件を使った.


TLE orz.. コンパイラのバージョンをjava7 にしたら通ったwww

Codeforces Div1 114 (167) C

02:31

問題:

(a,b) に対して,a<bとすると, (b % a, a), (a, b - a^k) k>0 とする操作が可能.

0 にしたら勝ち. どちらが勝つか.


解法:

まず,いずれ,(b%a, a)になることに注目する.

再帰的に,この状態が勝ちかどうかを判定. Loseなら,先手は即座に,(b%a, a)にすればよいので勝ち.

Win の場合が問題.

結局, (b%a, a) にしてしまったら負けなので, b-b%a 個の石があって,a^k 個とる操作ができて,石を0にしたら負け. というゲーム.

このゲームは, 周期 a*a+a で周期的になる. というのも,

a^i = a^(i%2) (mod a*a+a) が成立するので,

x - (a*a+a)j が負けなら,x も負け.

x - (a*a+a)j が勝ちなら,x も勝ち. というのも,x < a*a+a のときを考えてやると,負け状態は交互に並んでいるので,x%(a*a+a)>0 なる負けでない状態からは,aを取ることによって,負け状態にいける.

x%(a*a+a)==0 の時は,a*a を取ることによって,負け状態にいける.


a*a のoverflowに注意.

*1:共有する最初の点を選び,交差している中で,若い2つのsourceを逆転する,とすれば一対一対応になる.

 |