fork(1) download
copy 
  1. public class BagAndCards {
  2.  
  3.     int N;
  4.     final long mod = 1000000007;
  5.  
  6.     long power(long a, long b)
  7.     {
  8.         long ret = 1;
  9.         while(b > 0)
  10.         {
  11.             if(b % 2 == 1)
  12.                 ret = (ret * a) % mod;
  13.             a = (a * a) % mod;
  14.             b /= 2;
  15.         }
  16.         return ret;
  17.     }
  18.  
  19.     long inv(long x)
  20.     {
  21.         return power(x, mod - 2);
  22.     }
  23.  
  24.     class poly {
  25.         long[] c;
  26.         poly()
  27.         {
  28.             c = new long[N+1];
  29.         }
  30.  
  31.         long calcAt(long x)
  32.         {
  33.             long ret = 0, t = 1;
  34.             for(int i = 0; i <= N; i++)
  35.             {
  36.                 ret += t * c[i];
  37.                 ret %= mod;
  38.                 t = (t * x) % mod;
  39.             }
  40.             return ret;
  41.         }
  42.         void multiByXPlusB(long b)
  43.         {
  44.             for(int i = N; i >= 0; i--)
  45.             {
  46.                 c[i] = c[i] * b + (i == 0 ? 0 : c[i-1]);
  47.                 c[i] %= mod; c[i] += mod; c[i] %= mod;
  48.             }
  49.         }
  50.         void divideByXPlusB(long b)
  51.         {
  52.             for(int i = N; i >= 1; i--)
  53.             {
  54.                 c[i-1] -= c[i] * b;
  55.                 c[i-1] %= mod; c[i-1] += mod; c[i-1] %= mod;
  56.             }
  57.             for(int i = 0; i < N; i++)
  58.                 c[i] = c[i+1];
  59.             c[N] = 0;
  60.         }
  61.         poly add(poly that)
  62.         {
  63.             poly ret = new poly();
  64.             for(int i = 0; i <= N; i++)
  65.                 ret.c[i] = (c[i] + that.c[i]) % mod;
  66.             return ret;
  67.         }
  68.         poly mul(long t)
  69.         {
  70.             poly ret = new poly();
  71.             for(int i = 0; i <= N; i++)
  72.                 ret.c[i] = (c[i] * t) % mod;
  73.             return ret;
  74.         }
  75.     };
  76.  
  77.     long[][] f;
  78.     long[][] coef;
  79.     long[] coefPrime;
  80.  
  81.     public int getHash(int n, int m, int x, int a, int b, int c, String isGood)
  82.     {
  83.         N = 2 * m;
  84.         f = new long[n][N];
  85.         coef = new long[N][N];
  86.         coefPrime = new long[N];
  87.         for(int i = 0; i < n; i++)
  88.         {
  89.             poly t = new poly();
  90.             for(int j = 0; j < m; j++)
  91.             {
  92.                 t.c[j] = x;
  93.                 x = (int)(((1L * x * a + b) ^ c) % mod);
  94.             }
  95.             for(int j = 0; j < N; j++)
  96.                 f[i][j] = t.calcAt(j);
  97.         }
  98.  
  99.         // Lagrange Interpolation
  100.         poly prod = new poly();
  101.         prod.c[0] = 1;
  102.  
  103.         for(int i = 0; i < N; i++)
  104.             prod.multiByXPlusB(-i);
  105.  
  106.         for(int i = 0; i < N; i++)
  107.         {
  108.             prod.divideByXPlusB(-i);
  109.             long mul = 1;
  110.             for(int j = 0; j < N; j++)
  111.                 if(i != j)
  112.                 {
  113.                     mul = (mul * (i - j));
  114.                     mul %= mod; mul += mod; mul %= mod;
  115.                 }
  116.             mul = inv(mul);
  117.             for(int j = 0; j < N; j++)
  118.             {
  119.                 coef[j][i] = (coef[j][i] + prod.c[j] * mul) % mod;
  120.                 if(j < isGood.length() && isGood.charAt(j) == 'Y')
  121.                 {
  122.                     coefPrime[i] += prod.c[j] * mul;
  123.                     coefPrime[i] %= mod;
  124.                 }
  125.             }
  126.             prod.multiByXPlusB(-i);
  127.         }
  128.         long xors = 0;
  129.         for(int i = 0; i < n; i++)
  130.             for(int j = i+1; j < n; j++)
  131.             {
  132.                 long s = 0;
  133.                 for(int k = 0; k < N; k++)
  134.                 {
  135.                     s += (((coefPrime[k] * f[i][k]) % mod) * f[j][k]) % mod;
  136.                     s %= mod;
  137.                 }
  138.                 xors ^= s;
  139.             }
  140.         return (int)xors;
  141.     }
  142. }
  143.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class BagAndCards is public, should be declared in a file named BagAndCards.java
public class BagAndCards {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/XFomMa
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!