10/2 PKU

3012 A Number from Yanghui Triangle

パスカルの三角形上の数値を、桁揃えの0を入れた上で並べたものをMで割った余りを求めよ。

(10^K+1)^N mod Mを求めるだけ。

3213 PM³

行列A,B,Cがある。Cは、計算機がA*Bを計算した値である。しかし、計算機はたまに計算ミスをするので、Cが間違っているかもしれない。計算ミスをするときは、必ず1箇所だけ間違える。Cが正しいかどうかと、間違っていれば誤りを指摘せよ。

AはN*P、BはP*M、CはN*Mの行列である。Xを適当に作ったM*1の行列とすると、A*B*XはA*(B*X)として計算できる。C*Xも計算できる。答えとしてともにN*1の行列が生じるが、A*(B*X)とC*Xで違う箇所があるならそれはCのその行に誤りがあるからであるとわかる。A*B≠CなのにA*(B*X)=C*Xとなる確率は極めて低い(乱択アルゴリズム)。
同様に、Yを1*Nの行列として、Y*A*BとY*Cを比べると、Cの誤りの存在する列がわかる。
誤りの位置がわかったら、その位置だけ正しい値を計算してやればよい。

1694 An Old Stone Game

木構造の上でゲームをする。まずK個の石をバケットに入れておく。木構造の葉ノードにはいつでもバケットから石を持ってくることができる。子を持つノードは、すべての直接の子に石が置いてある時、それらをバケットに戻して、そのノードに石を置くことができる。根に石を置けば勝ちである。勝てるような最小のKを求めよ。

木DP

3978 Primes

[A,B]に含まれる素数の数を数えるだけの問題。自明