fork download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. const int mod=1e9+7;
  8. int dp[101][101][52], gcd[102][102];
  9.  
  10. int main()
  11. {
  12. 	for(int i=1; i <=100;i++)
  13. 	{
  14. 		for(int j = 1; j <= 100; j++)
  15. 		{
  16. 			gcd[i][j]=__gcd(i, j);
  17. 		}
  18. 	}
  19. 	int n, k, x;
  20. 	cin >> n >> x >> k;
  21. 	for(int j=1; j<=100; j++)
  22. 	{
  23. 		if(j==x) dp[1][j][1]=1;
  24. 		else dp[1][j][0]=1;
  25. 	}
  26. 	for(int i = 2; i <= n; i++)
  27. 	{
  28. 		for(int j = 1; j <= 100; j++)
  29. 		{
  30. 			for(int l=0; l <=k; l++)
  31. 			{
  32. 				ll sum=0;
  33. 				if(j==x)
  34. 				{
  35. 					if(l!=0)
  36. 					{
  37. 						for(int m = 1; m <= 100; m++)
  38. 						{
  39. 							if(gcd[m][j]==1)
  40. 							{
  41. 								sum+=dp[i-1][m][l-1];
  42. 								sum%=mod;
  43. 							}
  44. 						}
  45. 					}
  46. 				}
  47. 				else
  48. 				{
  49. 					for(int m = 1; m <= 100; m++)
  50. 					{
  51. 						if(gcd[m][j]==1)
  52. 						{
  53. 							sum+=dp[i-1][m][l];
  54. 							sum%=mod;
  55. 						}
  56. 					}
  57. 				}
  58. 				dp[i][j][l]=sum;
  59. 			}
  60. 		}
  61. 	}
  62. 	ll sum=0;
  63. 	for(int i = 1; i <= 100; i++)
  64. 	{
  65. 		sum+=dp[n][i][k];
  66. 		sum%=mod;
  67. 	}
  68. 	cout << sum;
  69. }
Runtime error #stdin #stdout 0s 17336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6sTXyi
language:
C++ (gcc 8.3)
created:
6 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!