EDPC M - Candies
EDPC M - Candies についてのメモを残します。
累積和の利用
- 問題 : EDPC M - Candies
番目の子どもまでで 個の飴を余りなく分け合う方法の総数
とし、 とする。
、 のとき、dp テーブルは下図のようになる。
疑似コードは以下の通り。
for i = 0 to N-1 for j = 0 to K for k = 0 to a[i] dp[i+1][j+k] += dp[i][j]
これだと で TLE となってしまうので、工夫が求められる。
からの遷移は、区間 に を加算しているので、いもす法を使って累積和を求める。
for i = 0 to N-1 for j = 0 to K dp[i+1][j] += dp[i][j] dp[i+1][j+a[i]+1] -= dp[i][j] for j = 0 to K-1 dp[i+1][j+1] += dp[i+1][j]
これで計算量は に抑えられる。
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; // val を m で割った余りを返す (負の余りは m を足す) long long mod(long long val, long long m) { long long res = val % m; if (res < 0) res += m; return res; } int main() { int N, K; cin >> N >> K; vector<int> A(N); for (int i = 0; i < N; i++) cin >> A[i]; // dp[i][j] := i 番目の子どもまでで j 個の飴を分け合う方法の総数 vector<vector<long long>> dp(N+1, vector<long long>(K+1, 0)); dp[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= K; j++) { // dp[i+1][*] への遷移 : 区間 [j, j + a_i] に dp[i][j] を加算 dp[i+1][j] += dp[i][j]; dp[i+1][j] = mod(dp[i+1][j], MOD); if (j+A[i]+1 <= K) { dp[i+1][j+A[i]+1] -= dp[i][j]; dp[i+1][j+A[i]+1] = mod(dp[i+1][j+A[i]+1], MOD); } } for (int j = 0; j < K; j++) { dp[i+1][j+1] += dp[i+1][j]; dp[i+1][j+1] = mod(dp[i+1][j+1], MOD); } } cout << dp[N][K] << endl; }