fork(3) download
copy 
  1. import java.util.*;
  2.  
  3. public class Main // WarAndPeas
  4. {
  5.     final long MOD = 1000000007;
  6.  
  7.     long modPow(long a, long b)
  8.     {
  9.         a %= MOD;
  10.         long ans = 1;
  11.         while (b > 0)
  12.         {
  13.             if (b % 2 != 0)
  14.                 ans = ans * a % MOD;
  15.             a = a * a % MOD;
  16.             b /= 2;
  17.         }
  18.         return ans;
  19.     }
  20.  
  21.     long add(long a, long b)
  22.     {
  23.         return (a + b) % MOD;
  24.     }
  25.     long sub(long a, long b)
  26.     {
  27.         return (a - b % MOD + MOD) % MOD;
  28.     }
  29.     long mul(long a, long b)
  30.     {
  31.         return a * b % MOD;
  32.     }
  33.     long div(long a, long b)
  34.     {
  35.         return mul(a, modPow(b, MOD - 2));
  36.     }
  37.  
  38.     int N;
  39.     int M;
  40.     int S;
  41.     long[][] pasc;
  42.  
  43.     int c2(int x)
  44.     {
  45.         return x * (x-1) / 2;
  46.     }
  47.  
  48.     public int expectedPeas(String state)
  49.     {
  50.         N = state.length();
  51.         M = c2(N);
  52.         for (int i = 1; i < N; i++)
  53.             if (state.charAt(i) == state.charAt(0))
  54.                 ++S;
  55.  
  56.         pasc = new long[N][N];
  57.         for (int i = 0; i < N; i++)
  58.             for (int j = 0; j < N; j++)
  59.                 if (j == 0) pasc[i][j] = 1;
  60.                 else if (j > i) pasc[i][j] = 0;
  61.                 else pasc[i][j] = add(pasc[i-1][j-1], pasc[i-1][j]);
  62.  
  63.         long[] B = new long[N];
  64.         for (int i = 0; i < N-1; i++)
  65.         {
  66.             int good = i;
  67.             int bad = N - i - 1;
  68.             long a = div(good * bad, 2 * M);
  69.             long b = div(c2(good) + c2(bad) + good, M);
  70.             long c = sub(1, a + b);
  71.             if (i != 0)
  72.                 B[i] = mul(B[i-1], a);
  73.             if (S == i-1)   B[i] = add(B[i], a);
  74.             if (S == i)     B[i] = add(B[i], b);
  75.             if (S == i+1)   B[i] = add(B[i], c);
  76.             B[i] = div(B[i], c);
  77.         }
  78.         for (int i = N-2; i >= 0; i--)
  79.             B[i] = add(B[i], B[i+1]);
  80.         long ans = 0;
  81.         for (int i = 0; i < N; i++)
  82.             ans = add(ans, mul(B[i], pasc[N-1][i]));
  83.         ans = div(ans, pasc[N-1][S]);
  84.         ++ans;
  85.         ans = div(ans, modPow(2, N));
  86.         return (int) ans;
  87.     }
  88.  
  89.     public static void main(String[] args)
  90.     {
  91.         System.out.println(new Main().expectedPeas(new Scanner(System.in).next()));
  92.     }
  93. }
Success #stdin #stdout 0.14s 321088KB
comments (?)
stdin
copy 
BAB
stdout
copy 
375000003
https://ideone.com/ggJ2qd
language:
Java (HotSpot 12)
created:
9 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!