TopCoder SRM 745 Div1 Medium Chains4

問題文の解釈が辛すぎて全然楽しめなかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=15262

問題

2つの非負整数x,yで定義される半開区間[x,y)の列のうち、前者が後者に含まれる、というような一連の列を考える。
（なお、長さ0の区間[0,0)、[1,1)…は同一とみなす)

整数nが与えられる。全体が[0,n)に収まるような区間列はいくつあるか。

解法

f(k) := 最後の要素が[0,k)であるような区間列の組み合わせ
とする。長さkの区間の直前に、長さ0～(k-1)の要素が含まれるケースを考えると、長さ0の区間列だけは位置に関わらず同一なので、直前に何も含まないケースも含めると

となる。
また、求める解はである。

f(k)を愚直に求めると1回あたりO(k)かかるので、全体でO(n^2)かかることになる。
ただf(k)間の差分は概ねsum(f(i))なのことからf(k)はO(1)で適宜求められるので全体でO(n)で抑えられる。

ll dp[20202];
ll mo=1000000007;

class Chains4 {
	public:
	int count(int n) {
		ll ret=1;
		dp[0]=1;
		ll M=0,S=0;
		for(int i=1;i<=n;i++) {
			dp[i]=2;
			(dp[i]+=M)%=mo;
			(S+=dp[i])%=mo;
			(M+=S+dp[i])%=mo;
			(ret+=(n+1-i)*dp[i])%=mo;
		}
		
		
		return ret;
	}
}

まとめ

この前のChain3の問題文の理解が辛すぎた…。