fork(1) download
copy 
  1. /*input
  2. 83 91 42
  3. */		
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. #define int ll
  9. typedef vector <int> vi;
  10. typedef vector<vi> vvi;
  11. typedef map<int,int> mii;
  12. typedef pair<int,int> pii;
  13. #define pb push_back
  14. #define INF 1000000000
  15. #define mp make_pair
  16. #define MOD 1000000007
  17. #define F first
  18. #define S second
  19. const double PI=3.141592653589793238462643383279502884197169399375105820974944;
  20. #define REP(i,n) for(int i=0;i<(n);i++)
  21. #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  22. #define REPD(i,n) for(int i=(n);i>=0;i--)
  23. #define FORD(i,a,b) for(int i=(a);i>=b;i--)
  24. #define all(v) v.begin(),v.end()
  25. #define itr ::iterator it
  26. #define WL(t) while(t --)
  27. #define gcd(a,b) __gcd((a),(b))
  28. #define lcm(a,b) ((a)*(b))/gcd((a),(b))
  29. #define remin(a,b) (a) = min((a),(b))
  30. #define remax(a,b) (a) = max((a),(b))
  31.  
  32. int n,x,k,dp[105][105][55];
  33. vi cop[105];
  34.  
  35. signed main() {
  36.  
  37. 	ios_base::sync_with_stdio(false);
  38. 	cin.tie(0);
  39. 	cout.tie(0);
  40.  
  41. 	cin >> n >> x >> k;
  42.  
  43. 	FOR(i,1,101){
  44. 		if(i == x) dp[1][i][1] = 1;
  45. 		else dp[1][i][0] = 1;
  46. 		FOR(m,1,101){
  47. 			if(gcd(i,m) == 1) cop[i].pb(m);
  48. 		}
  49. 	}
  50. 	FOR(i,2,n+1){
  51. 		FOR(j,1,101){
  52. 			FOR(l,0,(i+3)/2){
  53. 				int cur = 0;
  54. 				if(j == x){
  55. 					if (l == 0){
  56. 						dp[i][j][l] = 0;
  57. 						continue;
  58. 					}
  59. 					for(int m = 0; m < cop[j].size(); m++){
  60. 						cur += dp[i-1][cop[j][m]][l-1];
  61. 					}
  62. 					dp[i][j][l] = cur%MOD;
  63. 					continue;
  64. 				}
  65. 				for(int m = 0; m < cop[j].size(); m++){
  66. 					cur += dp[i-1][cop[j][m]][l];
  67. 				}
  68. 				dp[i][j][l] = cur%MOD;
  69. 			}
  70. 		}
  71. 	}
  72. 	int ans = 0;
  73. 	FOR(j,1,101) ans += dp[n][j][k];
  74. 	cout << ans%MOD << endl;
  75. }
Success #stdin #stdout 0s 20792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9QImAz
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!