2400的cf题,看到这个值以为很难
读完题目,觉得很简单,就是双向深搜
然而还是T了然后挂个fread竟然wa在样例1
(╥╯^╰╥)
题目链接
题意:
给出n, m, k, n$\times$m的矩阵
问从左上到右下有多少条路径
路径上点的总异或值等于k
只能往右或往下走
解法:
由于m, n最大值是20,如果直接深搜
复杂度是O($2^{m+n}$),也就是$2^{40}$,妥妥的TLE
但是如果双向搜索,起点搜一半,终点往回搜一半
复杂度就会降很多,O($2^{\frac{m+n}{2}}$),也就是$2^{20}$
路径很多,答案会爆int
由于有些路径在搜索的终点值一样,可以用map
代码:
1 |
|