SRM 613

250

枚举分隔的位置,左边的一起向左,右边的一起向右。统计答案即可。

500

看了WJMZBMR的代码才明白过来T_T,容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1,所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。

900

看了芒果的代码才明白过来。首先是不能一行一行来填,这样dp的状态太难表示。

然后考虑一列一列来填。

  1. 假如只有left的话,就可以f[i][j]来表示填好前i列,其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的,但是还没决定填在哪些行这么个意思。然后遇到left的结束端点,就可以拿这些数目去分配。大致就是乘个A几几的组合数。
  2. 现在如果有right的话,可以按left反过来那样处理,但是现在要统一起来,只能考虑从左往右填。由于一个行进入可填范围就不会变没了,所以f[i][j]表示填好前i列,还有j行没搞定。于是每次可以选择(或者不选)一个行,用当前列来填上。
  3. 最后把前两种dp合起来,f[i][j][k]转移一下就好了。

留下评论

您的电子邮箱地址不会被公开。