CodeChef October Challenge 2013 Editorial [Sereja and Transformation]

Problem: Sereja and Transformation
After wasting a lot time i finally understand the problem and figure out that K is totally valueless. difference of maximum and minimum element remains same after any time of operation.
you are given three integer.
N=number of array elements.
M= maximum limit value of array.
Q= difference of maximum and minimum element
You have to find how many ways you can put numbers in N position, where difference of maximum and minimum element is Q. and maximum element do not exceed M.
as the answer can be too large, print answer modulo 1e9+7.

Solution Idea: Inclusion/Exclusion
lets have an example first, for M=5 & Q=2, how many ways you can select minimum and maximum element?
way1 : min=1, max=3.
way2 : min=2, max=4.
way3= min= 3, max=5.
so, there is (M-Q) ways.

now calculate how many combination you can select array elements for way1?
as Q is the difference, you have Q+1 numbers.
Q+1 numbers can be place in N positions in (Q+1)^N ways. but you have to have minimum and maximum elements in each combination.
there is (2*Q^N+(Q-1)^N) combination where any of min or max is not present.

not clear yet?
ok, you have Q+1 numbers, if you can't use min, you have Q numbers that can be placed in Q^N ways.
similarly if you can't use max, you have another Q^N ways.
but wait, you removed some combination twice, add them.
for clarify, write down a small example in paper yourself and check the combinations.

as N is large enough as power, use BigMod.

Note: You can't make any combination if M<=Q.

Code:

1. #include<bits/stdc++.h>
2. using namespace std;
3.  
4. #define SET(a) memset(a,-1,sizeof(a))
5. #define CLR(a) memset(a,0,sizeof(a))
6. #define PI acos(-1.0)
7.  
8. #define MOD 1000000007
9. #define MX 100010
10.  
11. long long Bigmod(long long base, long long power)
12. {
13. long long ret=1;
14. while(power)
15. {
16. if(power & 1)
17. ret=(ret*base)%MOD;
18. base=(base*base)%MOD;
19. power>>=1;
20. }
21. return ret;
22. }
23.  
24.  
25. int main()
26. {
27. long long tc,kk=1, n, m, q, k;
28. cin>>tc;
29. while(tc--)
30. {
31. cin>>n>>m>>q>>k;
32. if(m<=q) cout<<0<<endl;
33. else cout<<((m-q)*(Bigmod(q+1, n) - (Bigmod(q, n)*2)%MOD + Bigmod(q-1, n)+ MOD)%MOD)%MOD<<endl;
34. }
35. return 0;
36. }