ABC178 D. Redistribution

問題

整数Sが与えられる。
すべての項が3以上の整数で総和がSである数列がいくつあるか求めよ。
答えは10^9+7で割ったあまりで求めよ。

制約

• 1 <= S <= 2000

解法1

dp[i] := 総和がiであるような数列の個数
を考える。

i-1以下がわかっていると考えると、dp[i]は、それらの数列に3以上の数字xを付け足したものは、dp[i+x]の個数の一部になる。
dp[0]=1として、iを小さい方から、dp[i]にxを追加したものをdp[i+x]に加えていけばよい。

  vector<mint> dp(S+1);
  dp[0] = 1;

  rep(i,S+1){
    REP(j,3,S+1){
      if(i+j < S+1){
        dp[i+j] += dp[i];
      }
    }
  }

計算量はO(S^2)。

解法2

整数Sをk個に分割する、と考える。条件として3以上とあるので、先に3*k個を割り当てておけば、S-3*kをk個に0以上割り当てると考えられる。

これは、写像12相で「n個の玉を区別しない、k個の箱を区別する、何も条件なし」の場合であり、Comb(n+k-1,n)で求められる。
したがって、n=S-3*kとして、各kで上記を求めれば良い。
kは、1以上で、S-3*k>=0であるようなkで求めて足し合わせれば良い。
(注意として、S-3*k=0のときも含む。nは0で、Comb(0+k-1,0)が1。)

modのCombは、factとinv_factを前計算O(S)しておけば、O(1)なので、O(S)。