phantom11's blog

Coefficient calculations
By phantom11, 13 years ago, In English
Can someone tell me how to calculate the coefficient of x^k in the term: (1+x+x^2......x^n1)(1+x+x^2+....x^n2)........(1+x+x^2.....n^m)
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Basically what you want to find is the number of ways to express k as a sum of m non-negative numbers (with some restrictions because of n1,n2...). The simple way to solve this is using DP. However, I am almost sure that one can come up with an analytic formula.
For dp, dp[i][j] -  the coefficient of x^j in the term: (1+x+x^2......x^n1)(1+x+x^2+....x^n2)........(1+x+x^2.....x^ni) . Then dp[i][j] = (SUM t = 0 to min(ni,j)) dp[i-1][j-t].
Comment : we move from left to right with "using" more and more brackets.At dp[i][j] - we "inlude" bracket i. 
dp[1][j] = 1 for all 0<=j<=n1 ; = 0 for n1<j<= k.

For analytic solution: for k from 0 to minimal of n1...nm (denote min) we can find the coefficient by using binomial expansion formula. After that if we want min+1, the result is binomial expansion - "the impossible ways". We can find latter as follows. Suppose n1<n2<...; min = n1. Then "impossible ways"=the coefficient before x^0 (its 1) in product of all brackets except the first (since there is no x^n1+1 to make the total product be x^n1+1).
But you need to explore cases where n1=n2 and so on. Up to you)

As for DP you can notice that we don't really need the full table but only dp[i-1][...] to find dp[i][...]. So we need only two linear arrays, which saves a lot of space.

I think if you don't know the exact formula and there is problem like that on the contest - there is no reason to find it, just use the easier solution (if its OK in terms of time and space complexity).

And I'm really sorry if my DP formula is wrong, but I hope you can guess what the approach is now.  
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Did you mean this in your dynamic approach:: for(j=0;j<=a[0];j++) dp[0][j]=1; p=a[0]; for(k=1;k
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Did you mean this in your dynamic approach::
     where a[] contains the upper limit of each term;m=no. of terms.
     for(j=0;j<=a[0];j++)
      dp[0][j]=1;
     p=a[0]; 
    for(k=1;k<m;k++)
                {
                    p+=a[k];
                    for(j=0;j<=p;j++)
                    {
                        sum=0;
                        for(z=0;z<=Math.min(j,a[k]);z++)
                        sum+=dp[k-1][j-z];
                        dp[k][j]=sum;
                        }
                }
    → Reply