fork download
copy 
  1. // solution.cpp
  2. // Compile: g++ -std=c++17 -O2 solution.cpp -o solution
  3. // Problem: maximize 2048-like score on n x m when you control moves and spawns.
  4. // Formula used: Answer = 2^(K+2) - 4K - 4  (mod MOD), K = n*m, special-case K=1 -> 0.
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. using u128 = __uint128_t;
  9. using i128 = __int128_t;
  10. using ull = unsigned long long;
  11. using ll = long long;
  12.  
  13. ull mul_mod_u128(ull a, ull b, ull mod){
  14.     if(mod == 0) return 0;
  15.     u128 res = (u128)a * (u128)b;
  16.     res %= (u128)mod;
  17.     return (ull)res;
  18. }
  19.  
  20. ull pow2_mod(i128 exp, ull mod){
  21.     // compute 2^exp % mod, exp >= 0
  22.     if(mod == 1) return 0;
  23.     ull base = 2 % mod;
  24.     ull res = 1 % mod;
  25.     while(exp > 0){
  26.         if((exp & 1) != 0) res = mul_mod_u128(res, base, mod);
  27.         base = mul_mod_u128(base, base, mod);
  28.         exp >>= 1;
  29.     }
  30.     return res;
  31. }
  32.  
  33. int main(){
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(nullptr);
  36.     unsigned long long n, m;
  37.     unsigned long long MOD;
  38.     if(!(cin >> n >> m >> MOD)) return 0;
  39.     i128 K = (i128)n * (i128)m; // up to 1e18 safe in i128
  40.  
  41.     if(MOD == 1){
  42.         cout << 0 << '\n';
  43.         return 0;
  44.     }
  45.  
  46.     if(K == 1){
  47.         cout << 0 % MOD << '\n';
  48.         return 0;
  49.     }
  50.  
  51.     // compute pow = 2^(K+2) % MOD
  52.     i128 exp = K + 2;
  53.     ull pow2 = pow2_mod(exp, MOD);
  54.  
  55.     // compute term = (pow2 - (4*K + 4)) mod MOD
  56.     // compute 4*K mod MOD
  57.     // K mod MOD:
  58.     ull Kmod = (ull)((u128)K % (u128)MOD);
  59.     ull fourK = mul_mod_u128( (ull)4 % MOD, Kmod, MOD );
  60.  
  61.     // subtract safely:
  62.     // ans = pow2 - fourK - 4 (mod MOD)
  63.     long long tmp = 0;
  64.     // do modular subtraction using unsigned arithmetic
  65.     ull ans;
  66.     // compute (pow2 + MOD - fourK) % MOD first
  67.     if(pow2 >= fourK) ans = (pow2 - fourK) % MOD;
  68.     else ans = (MOD - ((fourK - pow2) % MOD)) % MOD;
  69.     // subtract 4
  70.     if(ans >= (ull)4) ans = (ans - 4) % MOD;
  71.     else ans = (MOD - ((4 - ans) % MOD)) % MOD;
  72.  
  73.     cout << ans << '\n';
  74.     return 0;
  75. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3 3 117
stdout
copy 
19
https://ideone.com/MfA8uJ
language:
C++14 (gcc 8.3)
created:
5 hours 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!