Count Arrays

Count Arrays

Time limit: 1000 ms
Memory limit: 256 MB

You are given Q segments. For every 1 \le i \le Q, segment number i is [l_i,r_i].

A binary array of length N is considered good if and only if for each 1 \le i \le Q there is at least one position between l_i and r_i (inclusive) in this array that contains 0.

Find the number of good arrays.

Standard input

The first line contains two integers N and Q.

The next Q lines contain two integers each, l_i and r_i, representing the segments.

Standard output

Print the answer modulo 10^9+7 on the first line.

Constraints and notes

  • 1 \le N, Q \le 10^5
  • 1 \le l_i \le r_i \le N for each 1 \le i \le Q
Input Output Explanation

Good arrays are 000001010100101

Out of 32 possible arrays only one (11111) is bad.

 

英文题解:

 

Let's solve it using dynamic programming. We let dp[i] be the number of ways to place numbers on prefix of length i with 0 surely being the i-th position (for other positions we do not know, they can be either 0 or 1).

Let dp[0]=1 for convenience; for each position we store mx[i]=0 if there is no segment with such right endpoint, or we store mx[i]=l, where l is the maximum leftpoint of segments ending with i.

Go from left to right. Assume we are at position i now. We maintain the variable leftmost, which is maximum all over the mx[j] for j<i. Then, dp[i]=sum (dp[j]) for j>=leftmost and j<i. Why? Because we need to know, where the previous 0 could stand (as you remember we are trying to put 0 at position i). It can stand only in these j, because if there was pos<leftmost, then there would exist a segment, such that there is no zero in its bounds. So, we calculate dp[i] as follows. You can see that it can be done in O(1) time, since dp[i] equals to the sum on the segment, so we can maintain prefix sums of dp, and get the sum on segment in O(1).

The last step is to do the same transition for fictive position n+1 (calculate dp[n+1] =sum(...)), where n is the size of array. It is so because the answer is not dp[n] (cause 0 does not stand always in n-th position).

 

中文题解:

令f[i]表示钦定第i个数为0的方案数,那么首先第0个和第n+1个位置可以钦定为0,那么答案为f[n + 1]且 f[0] = 1。

发现若是令第i个位置为0,则他的方案数是其f[j] (i前面最靠后的左端点)到f[i-1]之和,

然后o(n)扫一遍即可。

c++代码如下:

 

2 + 1 =