fork(2) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #define mod 1000000000
  4.  
  5. int nCr[4444][4444];
  6.  
  7. void pre(){
  8.     for(int i=0;i<=4000;i++)
  9.         nCr[i][0] = 1 ;
  10.     for(int i=1;i<=4000;i++)
  11.         for(int j=1;j<=i;j++)
  12.             nCr[i][j] = ( nCr[i-1][j-1] + nCr[i-1][j] ) % mod ;
  13. }
  14.  
  15. long long f(int sum, int m)  //returns number of ways to arrange m values such that sum is sum
  16. {  // sum is n, m is k, ans is n+k-1Ck-1
  17. 	//old code
  18. 	//if(sum==0)return 1;
  19. 	//if(sum==1) return m;
  20. 	//long long ans=m;
  21. 	//for(int i=2; i<=sum; i++)  { ans*=((m+i-1.0)/(sum-i+2));  ans%=mod; }
  22. 	//return ans;
  23. 	//NEW CODE
  24. 	return nCr[sum+m-1][m-1];
  25. }
  26.  
  27.  
  28. long long array[2500][2500];  //dp solution
  29. long long temp[2500][2500];  //dp solution builder helper - stores cumulative of values in 'array'
  30. long long sum;
  31.  
  32. int main() 
  33. {	
  34. 	pre();
  35.  
  36. 	ios_base::sync_with_stdio(false);
  37. 	int t, n, m;
  38. 	cin>>t;
  39. 	while(t--)
  40. 	{
  41. 		cin>>n>>m;
  42. 		sum=0;
  43.  
  44. 		array[0][0] = 1;  //f(0,m);
  45. 		temp[0][0] = 1;  //array[0];
  46.  
  47. 		for(int i=1; i<=m; i++)
  48. 		{
  49. 			array[0][i] = f(i,m)%mod;
  50. 			temp[0][i] = (temp[0][i-1] + array[0][i])%mod;
  51. 			//cout<<array[0][i]<<" "<<temp[0][i]<<" -- ";
  52. 		}
  53.  
  54. 		for(int i=1; i<n; i++)  //for n rows
  55. 		{
  56. 			for(int j=0; j<=m; j++)
  57. 			{
  58. 				array[i][j] = (array[0][j]*temp[i-1][j])%mod;
  59. 			//	cout<<array[i][j]<<" ";
  60. 				if(j==0) temp[i][j]=1;
  61. 				else temp[i][j] = (temp[i][j-1] + array[i][j])%mod;
  62. 			}
  63. 		}
  64.  
  65. 		for(int i=0; i<=m; i++) { sum+=(array[n-1][i]); sum%=mod;}
  66. 		cout<<sum<<"\n";
  67. 	}
  68. 	return 0;
  69. }
  70.  
Success #stdin #stdout 0.43s 178048KB
comments (?)
stdin
copy 
5
1 1
2 2
2 3
1997 1977
123 765
stdout
copy 
2
25
273
632000000
128028672
https://ideone.com/vDBnr0
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!