[CodeChef XORSACK]Hououin Kyouma and Xorsack

中文版

The problem source is not easy to find, so the problem link is provided.

Definitions:
"A number set" is a set of numbers, "Number sets" means a lot of sets of numbers
"$bit_{i}$" is the $i$-th $bit$ of a number or $\oplus($elements of a number set$)$ ($\oplus$ is the sign of $XOR$)
"$X_{i}$" is number $X$'s $bit_{i}$ ($X$'s $i$-th $bit$)

One $bit$ by one $bit$, we can try maintain the number sets satisfy current conditions.

But the number of number sets is too large ($2^N$)!
What can we do?
It doesn't matter, we can save these $N$ numbers. (call it $s$, $s$ can represent all $2^N$ number sets)
At least later we still can get all the number sets, by enumerate "to choose or not to choose"(call it "choosing state") of each elements of $s$.

The first step is maintain all the number sets, whose $bit_{1}=K_{1}$.

Suppose that $K_{1}=0$
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has even number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=0$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We can prove that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$ (Why? Maybe you could figure out by yourself :))

So, what we should do is replace $s$ with $\{{elements\ (in\ original\ s),\ whose\ bit_{1}=0},s'\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

What if $K_{1}=1$?
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has odd number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=1$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We just know that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$
Why not make each number sets, which originally doesn't contain $v_{1}$, contains $v_{1}$,
and make each number sets, which originally contains $v_{1}$, does not contains $v_{1}$?

Therefore, what should we do was just replace $s$ with $\{\{$elements (in original $s$), whose $bit_{1}=0\},s'$ after modify its $v_{1}$'s choosing state$\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

The problem is, how to modify all number sets' $v_{1}$'s choosing state in $s'$?
We can know that choosing the same number twice, has the effect equals to not to choose the number.
Therefore, we just force it to choose an extra number, $v_{1}$.
For implementation, just let $K\oplus v_{1}$! (But I use another variable, $now$, to represent the changes of $K$)

The answer is $No$ if $v_{1}$ does not exist when we need it.
Or there's nothing going wrong until the last $bit$ is considered (That means there are still number sets satisfy the conditions), the answer is $Yes$

Time complexity: $O(31N)$ (My code enumerates $31$ $bit$s)

code:

[Codeforces 631E]Product Sum

Link

Definitions:
$SUM[i]=\sum_{k=1}^{i}A_{k}$

For each element, $A_{i}$, how does the characteristic of the array change if we move $A_{i}$ to position $j$?
It changes $A_{i}(j-i)+SUM[i]-SUM[j]$!

Enumerate $i$ and $j$, we get an $O(N^{2})$ solution.
How to speed up?

Treat $j$ as coordinate $x$.
Then we can treat $SUM[j]$ as a function $f(x)$, $A_{i}*j+SUM[i]-A_{i}*i$ as a line $ax+b$ ($a=A_{i},b=SUM[i]-A_{i}*i$)

What we should find is $\max\{(ax+b)-f(x)\}$, where $f(x)$ is a fixed function, $ax+b$ is a line depend on which $A_{i}$ we choose.

Now we have a new way to enumerate: $x$
Enumerate $x$, and find the line whose $ax+b$ is maximum.
Actually, we can use $deque$ to maintain the $convex\ hull$ of these lines.
For each $x$, we just find the corresponding point on the $convex\ hull$, $(x,y)$, $y$ is what we want to get (maximum $ax+b$).

On this picture, black straight lines are $ax+b$ we want to pick to form the $convex\ hull$, the green one.

How to build the $convex\ null$?
Well, this is a long story... Learn it!
(keywords: $monotone\ queue$,$slope\ optimization$)
(hints: sort the lines by their slopes, $a$)

By enumerating $x$ in increasing order, we can reach linear time complexity with the help of monotonicity of $x$, get the maximum $ax+b$ for every $x$.
Update maximum $ax+b-SUM[x]$, this is how much we can increase the characteristic of the array.
Initial characteristic of the array is $\sum_{i=1}^{N}A_{i}*i$

Time complexity：$O(N\log N)$ (remember that $sorting$ was required)

p.s. Actually, we can avoid $sorting$ to reach $O(N)$, that is, only allow element move toward one direction, then these $ax+b$ become rays (instead of lines), enumerate $x$ in that directions, and dynamic maintain the $convex\ hull$. Please remenber that it's required to do the same thing on another direction.
p.s. For $O(N)$ implementation, you can see this.

code:

[Codeforces 651E]Table Compression

Link

For simplicity, let's assume all values are different.
For each row, we can connect edges from cells of larger values to cells of smaller values.
Considering time and memory usage, we only add edges between cells of adjacent values. (So $sorting$ is required)
For each column, we do the same thing.

Therefore, we get a $DAG$ ($Directed\ Acyclic\ Graph$), whose root is the cell of the largest value.
Each cell becomes a node in the graph.
We can know that if there is an edge from $a$ to $b$, the value of $a$ must be larger than $b$
So, the low bound of maximum number in the compressed table is the height of the whole graph.
How to reassign values of each cell?
Let's reassign each cell's (Call the cell $u$) value to the height of the subgraph, whose root is $u$.
Now that the low bound is reached.

How to calculate the height of a subgraph?
Let $DP[u]$ be the height of the subgraph, whose root is $u$.
Then we can conclude the following recursive formula:
$DP[u]=\max(DP[v]+1,v$ is a child node of $u)$
Specially, if $u$ has no child node, $DP[u]=1$
$Memorized\ Search$ can be used to obtain amortized time complexity $O(1)$.

Now it's possible to have pairs of cells of same values.
We can know:
If two cells of same value are on the same horizontal position, or same vertical position
After compression, both cells' values should still be the same.
So we can treat both cells as one single cell. (A single node in the graph)
$Disjoint\ Sets$ can be used to perform the implementation.

Time complexity：$O(NM(\log M+\log N))$ ($sorting$ of $N$ rows and $M$ columns)

code:

[UVa 11895]Honorary Tickets

We can use priority_queue to maintain the current best choice
A state contains following information:
1. The expect value of number of lucky tickets (I use a pair of long long, $(u,d)$, to represent a fraction)
2. The total number of envelops (called $c$ later)

The possibility of getting from a bag is $\frac{\frac{u}{d}}{c}$, i.e. $\frac{u}{dc}$

Total time complexity: $O(K\log N)$

code:

[UVa 12906]Maximum Score

For simplicity, we call the sequence that fit the restriction of $x_{i}$ $S_{i}$.
We can know that the length of $S_{i}$ would not exceed number of $x_{j}$, such that $x_{j}\leq x_{i}$
If we sort the numbers in increasing order, all $S_{i}$ would reach the maximum length!
So we can calculate the first answer according to descriptions above.

For the second answer, we know that for each $S_{i}$, all values $<x_{i}$ on the left of $x_{i}$ must form a non-increasing sequence, all values$<x_{i}$ on the right of $x_{i}$ must form a non-decreasing sequence, or $S_{i}$ would not be able to reach the maximum length.
So the optimal permutations are composed of a non-increasing sequence and a non-decreasing sequence.

Let's sort the pairs: $\{(v_{k},f_{k})\}$
The number of such optimal permutations is $\prod_{i=1}^{P-1}  (f_{i}+1)$

If you don't know why, let's call the location of maximum values $peak$.
for every $v_{k}$, we have $f_{k}$ of such numbers, we can decide to put $0,1,2,...,f_{k}$ on the left of $peak$ and $f_{k},f_{k}-1,f_{k}-2,...,0$ on the right of $peak$, so there are $f_{k}+1$ ways to assign values of $v_{k}$. Therefore, you know, the number of ways to assign all $v_{k}$ is $\prod_{i=1}^{P-1}  (f_{i}+1)$. :)

Total time complexity: $O(P\log P)$

Note:
1. The first answer is no need to modulo $10^{9}+7$.
2. The first answer must be handled with unsigned long long, not long long.

code:

[UVa 12581]Divisibility

Let's try to figure out what's the value of $(x_{1},x_{2},x_{3},...)$.
We can discover that the value is the number of different paths from $(0,0,0,...)$ to $(x_{1},x_{2},x_{3},...)$, one step in the path is defined as increase one of the co-ordinates by one.

So we can know the value of $(x_{1},x_{2},x_{3},...)$ is $\frac{(\sum_{k=1}^{N}  x_{k})!}{\prod_{k=1}^{N}  (x_{k}!)}$
If you don't know why, image that there are $x_{1}$ $vectors$ of $(1,0,0,...)$, $x_{2}$ $vectors$ of $(0,1,0,...)$, and so on. Therefore, no matter how you permutate them, they always form a path from $(0,0,0,...)$ to $(x_{1},x_{2},x_{3},...)$, the number of such permutations is $\frac{(\sum_{k=1}^{N}  x_{k})!}{\prod_{k=1}^{N}  (x_{k}!)}$ (Let's call it $M$ later)

The problem is, in which condition $M$ is not divisible by P ?

We can just take only $P$'s multiples into consideration.
The number of factor $P$ in $n!$ is $\left[\frac{n}{P}\right]+\left[\frac{n}{P^{2}}\right]+\left[\frac{n}{P^{3}}\right]+...$
For simplicity, we call the value $f(n)$ (regard $P$ as constant)

Then M is not divisible by P if and only if $f(\sum_{k=1}^{N}  x_{k})=\sum_{k=1}^{N}  f(x_{k})$
i.e., for every $r\in\mathbb{N}$, $\sum_{k=1}^{N}  (x_{k}\mod P^{r})<P^{r}$ must hold.

If we transform every $n$ into $P-dicimal$ numbers, call it $T(n)$, then the above equation holds if and only if $\sum_{k=1}^{N}  (k_{th}$ digit of $T(x_{k}))<P$.

So be question becomes, how many set, $(x_{1},x_{2},x_{3},...)$, are there, such that for each $i\in\mathbb{N}$, $\sum_{k=1}^{N}  (i_{th}$ digit of $T(x_{k}))<P$ ?

Let's try to design a Dynamic Programming method to get the answer.
Suppose that we can enumerate from high digit to low digit.
A state includes the following information:
1. $i$, represent we are considering the $i_{th}$ digit now.
2. For every $T(x_{k})$, the range of its $(i-1)_{th}$ digit should be.(whether the $(i-1)_{th}$ digit has low bound or up bound)

For example, if the $i_{th}$ digit has a low bound of $a$, a up bound of $b$, the $(i-1)_{th}$ digit has no bounds if the $i_{th}$ digit$\in[a+1,b-1]$, has a low bound if the $i_{th}$ digit is $a$, has a up bound if the $i_{th}$ digit is $b$
Thus, we can update the values by enumerate the subsets of its set of bounds.
It's convenient to use bitmask to represent the sets.
Partial time complexity: $O(3^{2N}\log_{P}\max(x_{k}))$
However, we can optimize it by skipping if the value is 0.

Use another DP to calculate the number of cases, such that $\sum_{k=1}^{N} \{ i_{th}$ digit of $x_{k}$, within the given bound$\}<P$.
Partial time complexity: $O(NP)$.

Total time complexity: $O(3^{2N}NP\log_{P}\max(x_{k}))$.

code:

[UVa 12584]Laptop Chargers

Minimum how many chargers does he need to run all the laptops forever:
We can just sum up each discharge rate of the laptops, and then calculate how many chargers do we need to prevent total charge rate from being lower than the total discharge rate.
Explanation:
If total charge rate $<$ total discharge rate, you'll be sure to run out all your batteries someday.
Otherwise, with very fast charger switching, you can try to keep all your batteries from being lower than original conditions, and even better if possible.
For simplicity, we call the answer $\min M$

Maximum how long will he be able to run all his laptops using $M (M < N)$ chargers?
If $M\geq \min M$, the answer is, of course, $-1.000$.
Otherwise, we can come up with a simple method to get an "answer" first. That is, get total charge remaining in the laptop batteries(We call it $TR$ later), total discharge rate of laptops(We call it $TD$ later), and total charge rate of chargers(We call it $TC$ later)
Then we can get $\frac{TR}{TD-TC}$.
What's the problem if we treat it as the answer?
There exists some cases, such that one of the laptop battery is able to sustain for a very long time, even all other laptops have run out of battery with all chargers working.

So the problem is, which laptops don't need to be charged?
We can sort the laptops by the time they run out of battery without charger. For some $m$ ($m\geq M$), we can try use all chargers to make the first $m$ laptops run as long as possible, and see whether the $(m+1)$-th laptop can sustain until the first $m$ laptops are all run out of battery with all $M$ chargers working.

Find the first $m$ that the $(m+1)$-th laptop can sustain to the last. Then the answer is the time when the first $m$ are out of battery.
Otherwise, if we can't find such $m$, the "fake answer", $\frac{TR}{TD-TC}$, mentioned at first is printed.
Notice that if $TC\geq TD$ or $\frac{TR}{TD-TC}>100000$, you should always print "$-1.000$".

Time complexity: $O(N\log N+QN)$

Random inputs had been added to uDebug. :)

code:

[UVa 12590]Guards II

(Bottom is the English version)
這題的關鍵在排容原理
由於角落的守衛的特殊性(可以一次覆蓋兩條邊界)而且只有四個，我們不妨枚舉角落守衛的分配情況，然後再看看甚麼情況下可以覆蓋到所有邊界格子
定義：
Cover0(N,M,K)：N*M長方形中放K個守衛使得第1行到第M行都有守衛，符合條件的情況數量
Cover1(N,M,K)：和Cover0一樣，只是左上角那個點不能放守衛
Cover2(N,M,K)：和Cover1一樣，只是連右上角也不能放守衛(所以左上角和右上角都不能放)
以上的函數計算時間必須在O(max(N,M))以內

情況一：四個角落都沒有守衛
我們可以先計算四條邊界都至少有一位守衛的情況數量，這裡我使用排容原理
如果有一條邊界完全沒有守衛，假設是下邊界好了，有一些例外狀況是合法的：上面從左到右的每一行都至少有一個守衛
所以就用人海戰術把下邊界完全覆蓋起來了
這種例外狀況的數量是Cover2(N,M,K)
注意，和上邊界沒守衛的例外狀況會有重複的情況，因此相加之後要扣掉
重複情況的數量是Cover0(N,M,K)
另一個方向N、M互換就好

情況二：只有其中一個角落有守衛
為了方便說明，我們只討論守衛放在左上角的情況
一樣，我們可以先用排容原理計算右邊界和下邊界都至少有一位守衛的情況數量
然後也有一些例外狀況允許下邊界完全沒有守衛：上面從第2行到第M行都至少有一個守衛(因為第1行已經有角落的守衛了)
這種例外狀況的數量是Cover2(N,M,K)+Cover1(N,M,K)
另一個方向N、M互換就好

情況三：其中兩個相鄰的角落有守衛
為了方便說明，我們只討論守衛放在左上角和右上角的情況
一樣，我們可以先用排容原理計算下邊界至少有一位守衛的情況數量

也有一些例外狀況允許下邊界完全沒有守衛：上面從第2行到第M-1行都至少有一個守衛
這種例外狀況的數量是Cover2(N,M,K)+2*Cover1(N,M,K)+Cover0(N,M,K)
另一個方向N、M互換就好

情況四：其中兩個相對的角落有守衛
就算沒多放守衛也已經覆蓋所有邊界格子了
隨便亂放，數量為C(N*M-4,K-2)(四個角落已經決定好了要扣掉，而且已經用掉了兩個守衛)

情況五：其中三個角落有守衛
就算沒多放守衛也已經覆蓋所有邊界格子了
隨便亂放，數量為C(N*M-4,K-3)(四個角落已經決定好了要扣掉，而且已經用掉了三個守衛)

情況六：四個角落都有守衛
不想講了XD

注意到，上述的Cover0、Cover1、Cover2和C在計算過程中會被使用很多次，使用記憶化搜索可以大幅提升效率

上面的六個數字加權後加起來，就是答案了
別忘了隨時模1000000007以免爆long long

時間複雜度O(N*M*max(N,M)*K)

(English version)

The key point is inclusion-exclusion principle.
Because of the particularity of corner cells (if you place a guard here, he can cover two lines of border) and there are only four such cell, we can enumerate the allocation of corner guards, and then discuss, at what circumstances all border cells can be covered.
Definitions:
Cover0(N,M,K)：place K guards in N*M grid, such that each column from 1-st to M-th has at least one guard. The return value is the number of circumstances that meet the restrictions above.
Cover1(N,M,K)：Same as Cover0, but you can't place a guard at the up-left cell.
Cover2(N,M,K)：Same as Cover1, but you can't place a guard at the up-right cell(So you can place guard in neither up-left cell nor up-right cell).
Time complexities of functions above shouldn't exceed O(max(N,M)).

Case 1：All four corners are empty
First, we can calculate the number of circumstances, such that each of four lines of border has at least one guard, here I use inclusion-exclusion principle.
If there exist a line of border that has no guard, suppose it's down border.
There are still some exceptions that down border can be fully covered.
That is, each column has at least one guard exists.
So the down border is fully covered with human wave tactics.
The number of such exceptions is Cover2(N,M,K).
Notice that this will have duplicates with the exceptions of no guard on the up border, so after adding them together, we must deduct such duplicates.
The number of such duplicates is Cover0(N,M,K).
For another direction, just swap N and M, and handle it the same way.

Case 2: Only one corner has guard
For convenience, we only consider the guard to be placed at up-left corner.
Same as above, we can use inclusion-exclusion principle to get the number of circumstances, such that both down border and right border has at least one guard.
Also, there are exceptions that allow a empty down border.
That is, each column from 2-nd to M-th has at least one guard(Because column 1 already has a guard on the corner).
The number of such exceptions is Cover2(N,M,K)+Cover1(N,M,K).
For another direction, just swap N and M.

Case 3: Two of the adjacent corners has guard
For convenience, we only consider the guard to be placed at up-left corner and up-right corner.

The same, we can use inclusion-exclusion principle to get the number of circumstances, such that down border has at least one guard.

Again, there are exceptions that allow a empty down border.

That is, each column from 2-nd to (M-1)-th has at least one guard.
The number of such exceptions is Cover2(N,M,K)+2*Cover1(N,M,K)+Cover0(N,M,K).
For another direction, just swap N and M.

Case 4: Two of the opposite corners has guard
All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-2)(Four corners has been decided in advance and need to be excluded, and we've already used two guards).

Case 5: Three of the corners has guard
All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-3)(Four corners has been decided in advance and need to be excluded, and we've already used three guards).

Case 6: All of the four corners has guard
I don't want to say that again. XD

Please be noted that Cover0, Cover1, Cover2, and C might be calculated many times, so it's recommend to use memorized search to improve performance.

Weight the six numbers above and then plus them together, this should be the answer
Don't forget to module 1000000007 at any time for fear of overflowing~

Time complexity: O(N*M*max(N,M)*K)

code: