解題區/解題區 - UVa

UVa 11266 - Equations

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output:
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

Find the number of solutions, the equation ∑Xi = s have, if Ai≤Xi≤Bi for each i = 1…n.

For example,

X1 + X2 + X3 = 10

-1 ≤ X1 ≤ 3

2 ≤ X2 ≤ 4

6 ≤ X3 ≤ 7

The above set of equations has 6 solutions. They are: {1,4,7}, {0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.

You are given n the number of variables and the range of them. Your task is to calculate the number of solutions of that equation.

Input

First line of the Input contains T (≤50) the number of test cases. Then T test cases follow. First line of each test case contains 2 integer n (1≤n≤10) and s (-50000 ≤ s ≤ 50000). Next n lines each contain 2 integers describing the range of each variable. The ith line Ai and Bi (10000 ≤ Ai ≤ Bi ≤10000). Xi can take any integral value in the range [Ai, Bi].

Output:

For each test case output contains one integer denoting the number of solutions of the given equations. Output the value modulo 200003.

Sample Input

1
2
3
4
5
1
3 10
-1 3
2 4
6 7

Sample Output

1
6

Solution

題目描述：

對於每一個變數範圍，找到符合等式的解個數。

題目解法：

直接著手動態規劃，對於 dp[i][j] 定義為使用前 i 個變數，總合為 j 的方法數。

為了加快迴圈操作，必須修改成滑動窗口，為了省記憶體，又使用滾動數組。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int shift = 100000;
int dp[2][200005];
int main() {
    int testcase, n, s;
    int A[16], B[16];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &s);
        for(int i = 0; i < n; i++)
            scanf("%d %d", &A[i], &B[i]);
            
        memset(dp, 0, sizeof(dp));
        for(int i = A[0]; i <= B[0]; i++)
            dp[0][i + shift] = 1;
        int f = 1;
        for(int i = 1; i < n; i++) {
            memset(dp[f], 0, sizeof(dp[f]));
            int l = -B[i], r = -A[i], sum = 0;
            for(int j = 0 - B[i]; j <= 0 - A[i]; j++) {
                if(j < 0 || j >= 200005)
                    continue;
                sum += dp[!f][j];
                sum %= 200003;
            }
            for(int j = 0; j < 200005; j++) {
                dp[f][j] = sum;
                if(l >= 0 && l < 200005)
                    sum -= dp[!f][l];
                if(r + 1 >= 0 && r + 1 < 200005)
                    sum += dp[!f][r+1];
//				if(sum)
//					printf("%d %d %d\n", i, j - shift, sum);
                sum %= 200003;
                l++, r++;
            }
            f = !f;
        }
        printf("%d\n", (dp[!f][s + shift] + 200003)%200003);
    }
    return 0;
}