問題 問題概要 ビット列Sが与えられる。K以上の範囲を選んでその区間のSを反転させることができる時、最大のKを求めよ。 1<= |S| <= 105 解法 k文字目のみを変えようとした時、[0,k-1]->[0,k]を反転させることで変えることができる。 同様に[k+1,N]->[k,N]で…

問題 問題概要 ある路線には駅 1 から駅 N までの N 個の駅がある。 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。 連続する K個以上の駅に止まらないような組み合わせは何通り考えられるか、mod 109+7で求めよ。 2≤K≤N≤…

問題 問題概要 N以下の正整数であって、十進法表記したときの各桁の数の和がDの倍数であるものの個数をmod 1e9+7で求めよ。 1<=D<=102,1<=N<=10104 解法 dp[0][i][j] := (下からi桁までの数で、modがjであるものの数) dp[1][i][j] := (下からi桁までの数で、…

問題 問題概要 N,X,t[N]が与えられる。 スタミナXを持っていて、単位時間に1回復する。 t[i]にログインできるとして、j(1<=j<=N)回プレイした時に使える最大のスタミナはいくつか、全て出力せよ。 なおゲームをプレイするとその度に使い切るものとする。 1<=N…

問題 問題概要 自然数A,Bが与えられる。 A <= m <= Bなる自然数を選んだ全てが互いに素でなければならないという制約のもと非負整数個選ぶとき、選び方は何通りか。 1 <= A <= B <= 1018 B - A <= 35 解法 全探索して間に合う。その理由は解説参照。 特に6の…