Chef and Vectors
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has an integer array X, and a binary array S, both of size N. He wants to know how many vectors (denote by V) of N elements exist, for which the following conditions hold for all valid indices i (that is, for all 1 ≤ i ≤ N).
Please help Chef find this count. Since it may be a very large number, you should output the count modulo 109+7.
InputThe first line of input contains one integer N. The next N lines contain two integers each, with the ith containing Si and Xi. If Si = 0, then Vi ≤ Xi, otherwise Vi ≥ Xi.
OutputOutput a single line containing a single integer — the answer to Chef's problem modulo 109+7.
- 1 ≤ N ≤ 8
- 0 ≤ Xi < 1018
- Si is either 0 or 1.
Input: 2 0 22 0 30 Output: 6
There are 6 such vectors: (17, 30), (18, 29), (19, 28), (20, 27), (21, 26), (22, 25).
|Tags||cook65, digit-dp, dynamic-programming, hard, memoization, mgch|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.