fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ii pair<int,int>
  5. #define c_bit(i) __builtin_popcountll(i)
  6. #define Bit(mask,i) (((mask)>>(i)) & 1)
  7. #define onbit(mask,i) ((mask)| (1LL << (i)))
  8. #define offbit(mask,i)((mask) &~ (1LL <<(i)))
  9. using namespace std;
  10. const int MAXN=1e3+10;
  11. const int mod=1e9+7;
  12. int n,kmod;
  13. string dp[3*MAXN][MAXN][2][2]; int pre[3*MAXN];
  14. string sum(string x, string y){
  15. 	string res = "";
  16. 	int rem = 0;
  17. 	while(x.size() < y.size()) x = '0' + x;
  18. 	while(x.size() > y.size()) y = '0' + y;
  19. 	for (int i = x.size() - 1 ; i >= 0; -- i){
  20. 	    res = char((x[i] + y[i] - 2 * '0' + rem) % 10 + '0') + res;
  21. 	    rem = (x[i] + y[i] - 2 * '0' + rem) / 10;
  22. 	}
  23. 	if(rem > 0) res = char(rem + '0') + res;
  24. 	return res;
  25. }
  26. string dequ(int id,int M,int ok1,int ok2){
  27.     if(id > n){
  28.     	if(ok1 && ok2 && !M) return "1";
  29.     	return "0";
  30.     }
  31.     if(!dp[id][M][ok1][ok2].empty()) return dp[id][M][ok1][ok2];
  32.     string ans = ")";
  33.     for(int i = 0 ; i < 2 ; i ++){
  34.         for(int j = 0 ; j < 2 ; j ++){
  35.             for(int k = 0 ; k < 2 ; k ++){
  36.                 if((!ok1 && j < i) || (!ok2 && k < j)) continue;
  37.                 int m = (M + (i + j + k) * pre[n - id] * (id/3+1)) % kmod;
  38.                 ans = sum(ans, dequ(id + 1,m,ok1 || j > i,ok2 || k > j));
  39.             }
  40.         }
  41.     }
  42.     return dp[id][M][ok1][ok2] = ans;
  43. }
  44. int main()
  45. {
  46.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  47.     freopen("BEAUTIFUN.inp","r",stdin);
  48.     freopen("BEAUTIFUN.out","w",stdout);
  49.     cin >> n >> kmod; n = n * 3 - 1;
  50.     if(n == 0 || kmod == 0) return 0;
  51.     pre[0] = 1,pre[1] = 2,pre[2] = 4;
  52.     for(int i = 3 ; i < n ; i += 3) {
  53.         pre[i] = (pre[i-3] * 10 + 1) % kmod;
  54.         pre[i+1] = (pre[i-2] * 10 + 2) % kmod;
  55.         pre[i+2] = (pre[i-1] * 10 + 4) %kmod;
  56.     }
  57.     string ans = "0";
  58.     for(int i = 1 ; i <= 7 ; i ++){
  59.         for(int j = i ; j <= 7 ; j ++){
  60.             for(int k = j ; k <= 7 ; k ++){
  61.                 int ok1 = j > i;
  62.                 int ok2 = k > j;
  63.                 int m = ((i + j + k) * pre[n-2]) % kmod;
  64.                 ans = sum( ans, dequ(3,m,ok1,ok2) );
  65.             }
  66.         }
  67.     }
  68.     cout << ans;
  69.         cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
  70.     return 0;
  71. }
Success #stdin #stdout 0.1s 386388KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cyDWiL
language:
C++14 (gcc 8.3)
created:
8 days 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!