「题解」Emiya家今天的饭

众所周知，小葱同学擅长计算几何，但是并不擅长 DP。

• $m = 2/3$

设 $f[i,j,k]$ 表示考虑前 $i$ 行，第一列选了 $j$ 个，第二列选了 $k$ 个的方案数之和，有转移：$$f[i,j,k]\gets f[i-1,j-1,k]·a[i,1]+f[i-1,j,k-1]·a[i,2]$$ $m = 3$ 的情况也同理，多开一维状态就好了，复杂度 $O(n^3)$ 或 $O(n^4)$，能拿到 64pts。

• $m\le 500$

根据 lorem ipsum 原理，不合法方案中至多有一列的选择数超过 $\lfloor k/2 \rfloor$ ，则考虑补集转化，把不合法的方案 DP 出来。
钦点第 $u$ 行不合法，设 $f[i,j,k]$ 表示考虑前 $i$ 行，其它行一共选 $j$ 个， $u$ 行选了 $k$ 个的方案数，有转移：
$$ f[i,j,k]\gets f[i-1,j,k]+f[i,j,k-1]·a[i,u]+\sum\limits_{v\neq u} f[i,j-1,k]·a[i,v] $$ 预处理前缀和即可 $O(1)$ 转移，复杂度 $O(mn^3)$，能拿到 84pts。

代码：

for(int i = 1; i <= n; i++) ans = 1ll * ans * (a[i][0] + 1) % P; ans = (ans + P - 1) % P;
for(int u = 1; u <= m; u++){
    memset(f, 0, sizeof(f)), f[0][0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                f[i][j][k] = f[i - 1][j][k];
                if(k) f[i][j][k] = (1ll * f[i - 1][j][k - 1] * a[i][u] % P + f[i][j][k]) % P;
                if(j) f[i][j][k] = (1ll * f[i - 1][j - 1][k] * (a[i][0] - a[i][u] + P) % P + f[i][j][k]) % P;
            }
        }  
    }
    for(int j = 0; j <= n; j++)
        for(int k = 0; k <= n; k++){
            int s = (j + k) >> 1; if(k <= s) continue;
            ans = (ans - f[n][j][k] + P) % P;
        }
}

• $n\le 100, m \le 2000$

考虑削状态，设 $f[i,l]$ 表示考虑前 $i$ 行，$n+k-j=l$ 时的方案数，有转移：
$$ f[i,l]\gets f[i-1,l]+f[i-1,l+1]·a[i,u]+\sum\limits_{u\neq v}f[i-1,l-1]·a[i,v] $$ 预处理前缀和即可 $O(1)$ 转移，复杂度 $O(mn^2)$。

代码：

for(int i = 1; i <= n; i++) ans = 1ll * ans * (a[i][0] + 1) % P; ans = (ans + P - 1) % P;
for(int u = 1; u <= m; u++){
    memset(f, 0, sizeof(f)), f[0][n] = 1;
    for(int i = 1; i <= n; i++)
        for(int l = 0; l <= (n << 1); l++){
            f[i][l] = f[i - 1][l];
            f[i][l] = (1ll * f[i - 1][l + 1] * a[i][u] + f[i][l]) % P;
            if(l) f[i][l] = (1ll * f[i - 1][l - 1] * (a[i][0] - a[i][u] + P) % P + f[i][l]) % P;
        }
    for(int l = 0; l < n; l++) ans = (ans - f[n][l] + P) % P;
}