SRM 555

嗚嗚嗚。。。。最近感覺頭腦遲鈍啊

255：給你一個01序列，問你最少能将其分成幾段，使得每一段都不含前導0且都是5的幂次

一開始我是建了個最短路跑，後來發現兩個循環其實就可以搞定了。類似于dp，從前往後更新，沒發現一段區間合法就更新目前的dp值

import java.math.*;
import java.util.*;
public class CuttingBitString {
  boolean isPower(long number) {
    long s = 1;
    while(s < number) {
      s *= 5;
    }
    return s == number;
  }
  public int getmin(String S) {
    int n = (int)S.length();
    int [] dp = new int[n + 1] ;
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 0; i < n; i++) {
      if(dp[i] < Integer.MAX_VALUE && S.charAt(i) == '1') {
        long number = 0;
        for(int j = i; j < n; j++) {
          number = number * 2 + S.charAt(j) - '0';
          if(isPower(number)) {
            dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1) ;
          }
        }
      }
    }
    return dp[n] < Integer.MAX_VALUE ? dp[n] : -1;
  }
  void debug(Object...obj) {
    System.out.println(Arrays.deepToString(obj));
  }
}



// Powered by FileEdit
// Powered by moj 4.18 [modified TZTester]
// Powered by CodeProcessor
           

555：給你最大為1555 * 1555的一個全0 矩陣，對行操作Rcount次，對列操作Ccount次，一次操作是選擇一行或一列，0變1,1變0，

然後要使得最後的矩陣中1的個數為S個，問總的方案數，如果在某一行或一列上的操作次數是不同的，兩種方案就算不同方案

很水的一道題，意識到操作兩次等于沒操作就可以了。

枚舉x行是操作過的，y列是操作過的，剩下的Rcount - x,與Ccount - y都要成對成對的放到相應的行或者列，我是預處理了一個dp來做的。

f[i][j]表示j個物品放入i個不同的盒子的方案總數,可以為空(直接組合數也可以，我閑的當疼用dp)

f[i][j] = f[i-1][0] + f[i-1][1] + f[i-1][2]  + .. f[i-1][j];

import java.math.*;
import java.util.*;
public class XorBoard {
  final static int N = 2000;
  final static int mod = 555555555;
  public int count(int H, int W, int Rcount, int Ccount, int S) {
    int [][]f = new int[N][N];
    for(int i = 0; i < N; i++) {
      f[0][i] = 1;
    }
    for(int i = 1; i < N; i++) {
      for(int j = 0; j < N; j++) {
        if(j == 0) {
          f[i][j] = 1;
        } else {
          f[i][j] = f[i][j - 1] + f[i - 1][j];
          if(f[i][j] >= mod) {
            f[i][j] -= mod;
          }
        }
      }
    }
    int [][]c = new int[N][N];
    for(int i = 0; i < N; i++) {
      c[i][0] = c[i][i] = 1;
      for(int j = 1; j < i; j++) {
        c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        if(c[i][j] >= mod) {
          c[i][j] -= mod;
        }
      }
    }
    int ret = 0;
    for(int x = 0; x <= H && x <= Rcount; x++) { 
      for(int y = 0; y <= W && y <= Ccount; y++) {
        if((Rcount - x) % 2 == 0 && (Ccount - y) % 2 == 0) {
          if(W * x + y * H - 2 * x * y == S) {
            int a = (int)((long)c[H][x] * f[H - 1][(Rcount - x) / 2] % mod);
            int b = (int)((long)c[W][y] * f[W - 1][(Ccount - y) / 2] % mod);
            ret += (int)( (long) a * b % mod);
            if(ret >= mod) ret -= mod;
          }
        }
      }
    }
    return Integer.valueOf(ret);
  }
  void debug(Object...obj) {
    System.out.println(Arrays.deepToString(obj));
  }
}



// Powered by FileEdit
// Powered by moj 4.18 [modified TZTester]
// Powered by CodeProcessor