Codeforces Round #498 (Div. 3) F Xor-Paths

未分类

---

题目链接:http://codeforces.com/contest/1006/problem/F

题意:
一个$n*m$的矩阵,$a_{i,j}$表示第$i$行第$j$列的值.定义一条合法的路径为从$(1,1)$走到$(n,m)$,且只能往下或往右走,即$(i,j)$只能移动到$(i+1,j)$或者$(i,j+1)$,问有多少条合法的路径,满足路径上所有值的异或和为$x$.
数据范围:$1 \leq n,m \leq 20,1 \leq a_{i,j},x \leq 10^{18}$.

题解:
定义$n*m$的一条伪对角线为$S = \{(1,m),(2,m-1),...,(min(n,m),m-min(n,m)+1)\}$.
从$(1,1)$到$(n,m)$的某条合法路径会经过这些点中某一个点,且最多经过其中一个.
那么枚举$(i,j)\in S$,计算$(1,1)$到$(i,j)$的所有路径的异或值集合$A$和$(i,j)$到$(n,m)$所有路径的异或值集合$B$,然后枚举$A$中所有值,计算$B$中$x \oplus a[i][j]\oplus x$的个数,这个可以用$map$来完成计算.
复杂度计算:
最多计算$n$次,每次计算的复杂度是:

$$\begin{align*} f(i,j) & = (C_{i+j-2}^{i-1}+C_{n-i+1+m-j+1-2}^{n-i+1-1})*logn \\ & = (C_{m-1}^{i-1}+C_{n-1}^{n-i})*logn \\ & < (2^n+2^m)*logn \end{align*}$$
总时间复杂度是$O(min(n,m)*(2^n+2^m)*logn).$

$AC$ $code$:http://codeforces.com/contest/1006/submission/40446064