ほとんど公式解説と同じなので簡単に書きます。問題はこちら 問題概要 解説 提出プログラム 感想 問題概要2点がそれぞれ上下左右に移動することを回繰り返す．移動は左右にはの確率で，上下にはの確率で移動するとき、2点が回目の移動直後に初めて重なる確率…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要三次元グリッドのマスから隣り合う6つのマスのうち，いずれかのマスへの移動をちょうど回行った後にマスにいるような移動経路数を求めよ． 解説移動の仕方は対称なの…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要ある路線には駅から駅までの個の駅がある．準急は駅に止まり，{駅駅 }の部分集合に止まり，駅に止まる．連続する個以上の駅に止まると，客が飽きてしまうので，その…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要少し変えてます． で定義される数列の第項を求めよ．解説の母関数をとする．は形式的冪級数を用いてと表される． なので， のときは のときはしたがってBostan–Moriのアルゴリズムを用いるとで解け…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって，ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ．解説 が答えとなる(回の選択のうち，を選ぶ…

形式的冪級数を用いた珍しい(と思った)解き方がある問題集 (解けなかったやつも載せる)厳密には形式的冪級数ではないもの(有理数の指数が出るもの)も載せてる．ABC221 H 解説とする． なのでDP遷移がわかって解ける．ABC222 H 解説であるので はの逆関数とな…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列であって，以下の条件を満たすものの数を求めよ． 数列の総和が 解説とし，とすると， となるの組の数が答えとなる．したがってDPによりで求められる． で求めることもできる．kanpurin.h…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要について以下の値を求めよ． 個の正整数から多重集合のうち，以下の2つの条件をすべて満たすものの個数 要素の総和が 任意の正整数を高々個しか含まない 解説多重集…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上のからマンハッタン距離がの格子点に移動することを回繰り返すしたあとにいるとして，となる確率にをかけた値を求めよ．各格子点への移動確率はである…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上でからまでの最短経路の個数をとする．を求めよ．解説である．これは高校数学なので，分からない場合は復習が必要．次元累積和の典型みたいに考えると…

問題はこちら 問題概要 解説 形式的冪級数 提出プログラム 感想 問題概要全てのの組を以下のルールでソートしたときの番目の値を求めよ．上の方が優先度が高い． の昇順． の昇順． の昇順． 解説さすがに全部列挙するのは無理．の昇順に並んでいるので，全…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ．解説 形式的冪級数で解きます．とすると よってとしてが答え．を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり，線形漸化式に直し…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの整数列が与えられる. の部分列におけるスコアをと定義する. としてあり得るすべての数列のスコアの総和を求めよ.思考の流れ を全て列挙するのは無理なのでの寄与分を考えると, からまで…