fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #define M 1000000007
  3. using namespace std;
  4.  
  5. int m,n;
  6.  
  7. int DP(){
  8. 	int dp[n+1][m+1];
  9. 	for (int i=0;i<=n;i++){
  10. 		for (int j=0;j<=m;j++) dp[i][j] = 0;
  11. 	}
  12. 	for (int i=0;i<=m;i++) dp[n-1][i] = 1;
  13.  
  14. 	//exception handling
  15. 	long long temp = n,temp2 = m;
  16. 	long long int st = temp2-(temp*(temp+1))/2;
  17. 	if (st<0) return 0;
  18.  
  19. 	for (int i=n-2;i>=0;i--){
  20. 		for (int j=st;j>=st-(n-i)+1;j--){
  21. 			int k = 0;
  22. 			while(j-(n-i)*k>=0){
  23. 				dp[i][j] = (dp[i][j]+dp[i+1][j-(n-i)*k])%M;
  24. 				k++;
  25. 			}
  26. 		}
  27. 		for (int j=st-(n-i);j>=0;j--){
  28. 			dp[i][j] = (dp[i][j+n-i]-dp[i+1][j+n-i])%M;
  29. 			if (dp[i][j]<0) dp[i][j]+=M;
  30. 		}
  31. 	}
  32. 	return dp[0][st];
  33. }
  34.  
  35. int main(){
  36. 	int t,cs=1;
  37. 	scanf("%d",&t);
  38. 	while(t--){
  39. 		scanf("%d%d",&m,&n);
  40. 		printf("Case %d: %d\n",cs++,DP());
  41. 	}
  42. 	return 0;
  43. }
  44.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
2
40 3
12 3
stdout
copy 
Case 1: 114
Case 2: 7
https://ideone.com/jpHIlR
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!