fork download
copy 
  1. public class BearDestroys {
  2.     int mod;
  3.  
  4.     class Pair {
  5.         public int sum;
  6.         public int times;
  7.         public Pair(int sum, int times) {
  8.             this.sum = sum;
  9.             this.times = times;
  10.         }
  11.         public void modulo() {
  12.             sum %= mod;
  13.             times %= mod;
  14.         }
  15.     }
  16.  
  17.     public int sumUp(int W, int H, int mod_) {
  18.         mod = mod_;
  19.         Pair cells[] = new Pair[H*W];
  20.         int iii = 0;
  21.         for(int s = 0; s <= W + H - 2; ++s)
  22.             for(int y = 0; y < H; ++y) {
  23.                 int x = s - y;
  24.                 if(0 <= x && x < W)
  25.                     cells[iii++] = new Pair(x, y);
  26.             }
  27.         assert(iii == H * W);
  28.  
  29.         final int M = 1 << (H + 1);
  30.         Pair dp[] = new Pair[M];
  31.         for(int i = 0; i < M; ++i) dp[i] = new Pair(0,0);
  32.         dp[0] = new Pair(0, 1);
  33.         for(iii = 0; iii < H * W; ++iii) {
  34.             int x = cells[iii].sum, y = cells[iii].times;
  35.             int bitRight = -1, bitDown = -1;
  36.             for(int j = 1; j <= H + 3 && iii + j < H * W; ++j) {
  37.                 int xx = cells[iii+j].sum;
  38.                 int yy = cells[iii+j].times;
  39.                 if(x + 1 == xx && y == yy) bitRight = j;
  40.                 if(x == xx && y + 1 == yy) bitDown = j;
  41.             }
  42.             Pair old[] = new Pair[M];
  43.             for(int i = 0; i < M; ++i) {
  44.                 old[i] = new Pair(dp[i].sum, dp[i].times);
  45.                 dp[i] = new Pair(0, 0);
  46.             }
  47.             for(int mask = 0; mask < M; ++mask) {
  48.                 Pair me = old[mask];
  49.                 Boolean right = (0 == (mask & (1 << bitRight)) && x != W-1);
  50.                 Boolean down = (0 == (mask & (1 << bitDown)) && y != H-1);
  51.                 if(0 != (mask & 1) || (!right && !down)) {
  52.                     int m = mask / 2;
  53.                     dp[m].sum += 2 * me.sum % mod;
  54.                     dp[m].times += 2 * me.times % mod;
  55.                     dp[m].modulo();
  56.                     continue;
  57.                 }
  58.                 Boolean prefer = false;
  59.                 for(int hack = 0; hack < 2; ++hack) {
  60.                     int m;
  61.  
  62.                     if(right && (prefer || !down))
  63.                         m = mask / 2 + (1 << (bitRight-1));
  64.                     else
  65.                         m = mask / 2 + (1 << (bitDown - 1));
  66.                     dp[m].sum += (me.sum + me.times) % mod;
  67.                     dp[m].times += me.times;
  68.                     dp[m].modulo();
  69.                     prefer = true;
  70.                 }
  71.             }
  72.         }
  73.         return dp[0].sum;
  74.     }
  75. }
  76.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class BearDestroys is public, should be declared in a file named BearDestroys.java
public class BearDestroys {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/DEc6To
div1hard
language:
Java (12.0.1)
created:
8 years ago
visibility:
secret

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!