Hatena::Grouptopcoder

tsubosakaの日記

2009-01-19

SRM 320 Div1 Hard

| 19:08

n*m <= 80なのでmin(n,m) <= 8で一般性を失うことなく短い方を列としてよい.あとは現在の列の状態と配置したcheaterの数を状態としてDP.

すべての場合の数は\binom{n * m}{k}で求まる.なお\binom{80}[20} < 2^63より計算結果はlongに収まる.

import java.math.BigInteger;
import java.util.*;

public class SeatingPlan {
  List<Integer> accept(int m){
    List<Integer> res = new ArrayList<Integer>();
    l: for(int i = 0 ; i < (1 << m) ; i++){
      for(int j = 0 ; j + 1 < m ; j++)
        if((i & (1 <<j)) != 0 && (i & (1 <<(j+1))) != 0)
          continue l;      
      res.add(i);
    }    
    return res;
  }
  public String expectedTrial(int m, int n, int k) {
    if(m > n)return expectedTrial(n, m, k);
    List<Integer> alist = accept(m);
    int accept[] = new int[alist.size()];
    for(int i = 0 ; i < accept.length ; i++)
      accept[i] = alist.get(i);
    long memo[][] = new long[1 << m][k + 1];
    memo[0][0] = 1;   
    for(int col = 0 ; col < n ; col++){
      long next[][] = new long[1 << m][k + 1];
      for(int S : accept){
        for(int T : accept){
          if((S & T) != 0)continue;
          int i = Integer.bitCount(S);
          for(int a = 0 ; a <= k ; a++){
            if(a + i > k)break;
            next[S][a + i] += memo[T][a];
          }
        }
      }
      memo = next;
    }
    long sum = 0;
    for(int i = 0 ; i < memo.length ; i++)
      sum += memo[i][k];
    if(sum == 0)return "Impossible!";
    long tot = comb(m * n , k);
    return toStr(tot , sum);
  }
  long comb(int n , int k){
    long c[][] = new long[n + 1][n + 1];
    c[0][0] = 1;
    for(int i = 1 ; i <= n ; i++){
      c[i][0] = 1;
      for(int j = 1 ; j <= n ; j++){
        c[i][j] = c[i-1][j-1] + c[i-1][j];
      }
    }
    return c[n][k];
  }
  String toStr(long t , long s){
    BigInteger a = BigInteger.valueOf(t);
    BigInteger b = BigInteger.valueOf(s);
    BigInteger g = a.gcd(b);
    a = a.divide(g);
    b = b.divide(g);
    return a.toString() +"/" + b.toString();
  }
}

WilliamTagWilliamTag2019/02/02 11:26cialis over night
medicus group buy cialis
<a href=https://greatwinesgrandhouses.com>Cheap cialis buy online</a>
does cialis get you hard
cheapest cialis 20mg
https://kellyannehulme.com
buy cialis montreal
generic cialis in 2.5mg daily tablets
<a href=https://kellyannehulme.com>20 mg cialis</a>
lilly cialis without prescription
cialis brand name usa price
https://greatwinesgrandhouses.com

WilliamTagWilliamTag2019/02/02 11:26cialis ads
buying cialis in canada online
<a href=https://greatwinesgrandhouses.com>buy Cialis 20 mg</a>
liquid cialis does it work
cialis and avodart
https://kellyannehulme.com
what does cialis cost in mexico
cialis venezuela
<a href=https://greatwinesgrandhouses.com>Cheap cialis</a>
the cheapest cialis online
headache after cialis
https://greatwinesgrandhouses.com

ArnoldNizArnoldNiz2019/02/05 20:50canada drug generic cialis
buy generic cialis from canada
<a href="http://xcialisxx.com">Cheap Cialis</a>
snort cialis
cialis online con ricetta
<a href="http://cialistlm.com">Cheap Cialis buy</a>
brand cialis online mastercard
quick ship cialis
<a href="http://xcialisxx.com">Cheap Cialis</a>