LG 5664 Emiya-家今天的饭

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转题意:给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选,给出每个节点的选择方案数,求总方案数解法考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列我们可以用总方案数减去不符合的$si=\sum{j=1}^m a_{ij}$总方案数:$\prod_{i=1}^n (s_i+1) - 1$$\because k=\frac {tot}2$所以我们有一个很妙的方法:设选中目标行之外的权值+1,不选+0,选中目标行权值位+2 最后只要权值$> n……