fork download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3. #define Max 761238923
  4. using namespace std;
  5.  
  6. 	int n;
  7. unsigned	long long ans,dp[101][101];
  8. unsigned long long rec(int ind,int prev)
  9. {
  10. 	if(ind==n)
  11. 	{
  12.  
  13. 		return 1;
  14. 	}
  15.  
  16. 	if(dp[n-ind][n-prev]!=-1)
  17. 		return dp[n-ind][n-prev];
  18.  
  19.  
  20. 	dp[n-ind][n-prev]=0;
  21.  
  22.  
  23. 	for(int j=0;j+prev<=ind;j++)
  24. 	{
  25. 		dp[n-ind][n-prev]+=rec(ind+1,j+prev);
  26. 	if(dp[n-ind][n-prev]>=Max)
  27. 	dp[n-ind][n-prev]%=Max;
  28. 	}
  29. 	return dp[n-ind][n-prev];
  30.  
  31. 	}
  32.  
  33. int main() {
  34.  
  35. 	int i,j;
  36. 	for(i=0;i<=100;i++)
  37. 	for(j=0;j<=100;j++)
  38. 	dp[i][j]=-1;
  39.  
  40. 	//scanf("%d",&t);
  41. 	while(1)
  42. 	{
  43. 		scanf("%d",&n);
  44.  
  45. 		if(!n)
  46. 		return 0;
  47. 		ans=0;
  48. 		ans=rec(1,0);
  49. 		printf("%lld\n",ans);
  50.  
  51.  
  52. 	}
  53. 	return 0;
  54. }
  55.  
Success #stdin #stdout 0s 3380KB
comments (?)
stdin
copy 
1
2
3
4
50
100
0
stdout
copy 
1
2
5
14
192276108
116769572
https://ideone.com/MKOA5y
language:
C++ (gcc 8.3)
created:
9 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!