CS Academy--Binary Flips

未分类

---

题目：
　　给定一个$N*M$的$01$数组，数组元素初始值都是$0$.
　　你需要对数组进行$K$次操作，每次操作选定一个位置$(x,y)$，分别将第$x$行和第$y$列的全部元素翻转（$0$变成$1$，$1$变成$0$）.
　　问有多少种进行操作的方法使得$K$次操作后数组总共有$S$个为$1$.
　　$(1\leq N,M,K \leq 3000,0\leq S\leq N*M)$

题解：
　　假设最后有$i$行和$j$列总共被翻转了奇数次，那么总共有$iM+jN-2ij$个格子为$1$.
　　分别考虑行和列，对行来说，设$dp(i,j)$表示进行$i$次操作之后有$j$行被翻转奇数次的操作种数，显然：

$$\begin{align*} dp(i,j)&=dp(i-1,j-1)*(n-j+1)+dp(i-1,j+1)*j \\ \end{align*}$$
　　初始化$dp(0,0)=1$.
　　对列的操作同理，设为$h(i,j)$.
　　那么：
$$ans=\sum_{i=0}^{N}\sum_{j=0}^{M}[iM+jN-2ij=S]*dp(K,i)*h(K,j)$$
　　总时间复杂度是$O((N+M)K+N*M)$，空间复杂度$O((N+M)K)$.
　　显然每个$i$最多对应一个$j$使答案合法，可以直接求出$j$而不需要暴力，时间复杂度可以降为$O((N+M)K+min(N,M))$，不过在这个数据范围下仅仅算是常数优化.