project euler 113
对于1个数字，如果他数位不减或者不增称为bouncy number，比如1233，33210。统计1～10^100中的bouncy number
思路：分为两种计算
1.这个数中只出现了一个数字，那么对于i位的数字有9种，故总计有9 * 100种
2.这个数中至少出现两个数字，分别按位数计算不减的数和不增的数
以不减的数为例，枚举首数字j和尾数字k(j < k)，
j = a1 <= a2 <= a3 <= a4 <= a5 <= … <= am = k
令x1 = a2 - a1，x2 = a3 - a2, x3 = a4 - a3, …, xm - 1 = am - am-1。
x1 + x2 + x3 + … + xm-1 = k - j 解不定方程的解，C(k - j + m - 2, k - j)
不增的数同理
import java.util.*;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger; public class Main {
BigInteger bi(int x) {
return BigInteger.valueOf(x);
}
BigInteger comb(int n, int m) {
BigInteger ret = bi(1);
for (int i = n; i >= n - m + 1; -- i) ret = ret.multiply(bi(i));
for (int i = 1; i <= m; ++ i) ret = ret.divide(bi(i));
return ret;
}
void solve() {
int n = 100;
BigInteger ans = bi(9 * n);
for (int i = 2; i <= n; ++ i) {
for (int j = 1; j <= 8; ++ j)
for (int k = j + 1; k <= 9; ++ k) {
ans = ans.add(comb(k - j + i - 2, k - j));
}
}
for (int i = 2; i <= n; ++ i) {
for (int j = 1; j <= 9; ++ j)
for (int k = 0; k <= j - 1; ++ k) {
ans = ans.add(comb(j - k + i - 2, j - k));
}
}
System.out.println(ans);
}
FastScanner cin;
PrintWriter out;
void run() {
cin = new FastScanner();
out = new PrintWriter(System.out);
solve();
out.flush();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext; public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
hasNext = true;
} // public FastScanner(String s) {
// try {
// br = new BufferedReader(new FileReader(s));
// } catch (FileNotFoundException e) {
// // TODO Auto-generated catch block
// e.printStackTrace();
// }
// hasNext = true;
// } public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext() {
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null) next = nextToken();
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
return Long.parseLong(nextToken());
} public double nextDouble() {
return Double.parseDouble(nextToken());
}
}
public static void main(String[] args) {
new Main().run();
}
}