[CQOI2011]放棋子
发布时间:2020-12-14 04:17:39 所属栏目:大数据 来源:网络整理
导读:想到了50%吧算是。 f[i][j][k]表示,前i种,占了j行k列。方案数。 发现,转移要处理:“用c个棋子,占据n行m列”的方案数。 设g[i][j][k]表示,i行j列用k个棋子占的方案数。直接处理复杂度爆炸。 然后我就mengbier了。 考虑大力容斥: 也即,总方案数-不合法
想到了50%吧算是。 f[i][j][k]表示,前i种,占了j行k列。方案数。 发现,转移要处理:“用c个棋子,占据n行m列”的方案数。 设g[i][j][k]表示,i行j列用k个棋子占的方案数。直接处理复杂度爆炸。 然后我就mengbier了。 考虑大力容斥: 也即,总方案数-不合法方案数(不能覆盖完全) g[i][j][k]=C(i*j,k)-∑l∑r:g[l][r][k]*C(i,l)*C(j,r) (i*j>=k&&l<=i&&j<=r) 显然由于l,r不同,不会减多。 发现不用统计所有的 k,只用统计那c个即可。 然后f[i][j][k]的转移就顺理成章了。 复杂度:O(n^2m^2c) ? 总结: 没有想到容斥那一步。。。 正难则反。 最关键的是,不用k之间的递推,所以,第三维看似是k,其实是c(10而已) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |