http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=442
求解
x1 + x2 + x3 + .... + xn = m
其中xi属于[L, R]
不同解的个数。
这题需要用大数，要注意。
原理和以前做的一样。容斥。先算出每个xi大于等于Li的解的个数。关于这个，怎么解，看看：
http://www.cnblogs.com/liuweimingcprogram/p/6091396.html
然后容斥吧，枚举有一个数破坏条件，就是大于R的，减掉，两个，加回来。
由于每个R都不同，所以只能暴力dfs。也就是2^n的复杂度。
所以复杂度需要2^n * 常数。
推荐几个题吧。
http://www.cnblogs.com/liuweimingcprogram/p/6134521.html
http://www.cnblogs.com/liuweimingcprogram/p/6135008.html
一样的容斥思路的。
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/ /**
*
* @author Liu
*/
import java.util.*;
import java.math.*; //大数头文件
public class Main {
static final int maxn = 15;
static int[] be = new int[maxn];
static int[] en = new int[maxn];
static int n, m;
static BigInteger ans;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int t = input.nextInt();
while ((t--) > 0) { //返回值必须bool
n = input.nextInt();
m = input.nextInt();
int sum = 0;
for (int i = 1; i <= n; ++i) {
be[i] = input.nextInt();
en[i] = input.nextInt();
sum += be[i];
}
ans = BigInteger.ZERO; //清0
dfs(1, sum, 0);
System.out.println(ans);
}
}
public static BigInteger C(int n, int m) { //这个数字很大
if (n < m) return BigInteger.ZERO;
if (n == m) return BigInteger.ONE;
BigInteger ans = BigInteger.ONE;
int mx = Math.max(n - m, m); //调用最大值
int mi = n - mx;
for (int i = 1; i <= mi; ++i) {
ans = ans.multiply(BigInteger.valueOf(mx + i)); //转换成大数的方法
ans = ans.divide(BigInteger.valueOf(i)); //记得接收返回值
}
return ans;
}
public static void dfs(int cur, int tot, int has) {
if (cur == n + 1) {
if (has % 2 == 1) {
ans = ans.subtract(C(m - tot + n - 1, n - 1));
} else ans = ans.add(C(m - tot + n - 1, n - 1));
return;
}
dfs(cur + 1, tot - be[cur] + en[cur] + 1, has + 1);
dfs(cur + 1, tot, has);
}
}