fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define mod 1000000007
  5. int n;
  6. int dp[1000001][2][2];
  7. int solve(int in, int ze, int ni)
  8. {
  9. 	if (in == n)
  10. 	{
  11. 		if (ze && ni)
  12. 		{
  13. 			return 1;
  14. 		}
  15. 		return 0;
  16. 	}
  17. 	int ans = 0;
  18. 	if (dp[in][ze][ni] != -1)
  19. 	{
  20. 		return dp[in][ze][ni];
  21. 	}
  22. 	for (int i = 0; i <= 9; i++)
  23. 	{
  24. 		ans = ans + solve(in + 1, ((i == 0) ? 1 : ze), ((i == 9) ? 1 : ni));
  25. 		ans %= mod;
  26. 	}
  27. 	return dp[in][ze][ni] = ans;
  28. }
  29. int32_t main()
  30. {
  31. 	ios_base::sync_with_stdio(0);
  32. 	cin.tie(0);
  33. 	cout.tie(0);
  34. 	int tc = 1;
  35. 	while (tc--)
  36. 	{
  37. 		memset(dp, -1, sizeof(dp));
  38. 		cin >> n;
  39. 		cout << solve(0, 0, 0);
  40. 	}
  41.  
  42. 	return 0;
  43. }
Success #stdin #stdout 0.01s 34664KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NdWyPZ
language:
C++ (gcc 8.3)
created:
4 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!