Typical DP Contest F - 準急

• 問題

問題概要

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

解法

駅に止まる→1 止まらない→0とすると、1がK個以上連続しないN個のbit列を考えれば良い。
1がK個以上連続しない条件を満たすためには、 i個目に1を置こうとした時、最後に0を置いたのがi-K+2,..,i-1のどこかであり、 i個目に0を置こうとした時、最後に0を置いたのがi-K+1,i-K+2,..,i-1のどこかであれば良い。
すると、dp[i]:=(最後に0を置いたのがi番目であるようなビット列)と考えれば重複なく数え上げられ、漸化式も立てられることがわかる。
この時、1番目、N番目には1を置かなければならないのでdp[1]=dp[N]=0。 また0番目には0があるとして、dp[0]=1とする。
漸化式はdp[i] = sum(i-K+1<=j<=i-1)(dp[j]) (i != 1,N) となる。これを累積和で処理するとO(N)。
i=N+1まで計算すれば、dp[N+1]はN+1に0を置く場合の数で、dp[N]=0としているからN番目には1が置かれていることになる。
よってdp[N+1]は答えと一致する。

メモ

最初O(N²)のdpを考えたがオーダーを落とせなかった。
意外とO(N)の解法を最初から考えた方がよかったかもしれない。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 1000006, MAX_C = 102;
const ll lmod = 1e9+7;

ll sum[MAX_N],dp[MAX_N];

int main(){
  int N,K; cin >> N >> K ;
  sum[1] = dp[0] = 1LL;
  dp[1] = dp[N] = 0LL;
  // sum[i] := [0,i)のdpの和
  REP(i,1,N+2){
    if(i!=1 && i!=N) dp[i] = (sum[i] - sum[max(0,i-K)] + lmod) % lmod;
    sum[i+1] = (sum[i] + dp[i] + lmod) % lmod;
  }
  cout << dp[N+1] << endl;
  return 0;
}