shakil_AUST's blog

By shakil_AUST, 9 years ago, In English

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I don't know how to solve it using Inclusion-Exclusion. I have DP solution.

vi dp(v + 1, 0);
dp[0] = 1;
for (int i = 0; j < d.size(); ++i)
{
  vi dpNew(dp.size(), 0);
  for (int j = 0; j < dp.size(); ++j)
  {
    int cnt = 0; //this value can be computed in O(1)
    // { 
    for (int k = 0; k <= d[i]; ++k)
      if (k * c[i] <= j)
        cnt += dp[j - k * c[i]];
    // }
    dpNew[j] = cnt;
  }
  dp.swap(dpNew);
}
return dp[v];

To compute cnt value in O(1) split dp array into c[i] arrays.
Array number x has elements with numbers { x, x + c[i], x + c[i] * 2... }.
cnt value is equal to sum of integers on some subarray of array number j % c[i].
You have to construct prefix-sum array for each array to cumpute it.