6
14
2016
0

【NOI2015】【数论】【状压DP计数】寿司晚宴

题意:NOI的风格与UR的题目风格蛮像,很好的想法题。

/(有n-1个数分别为2~n,两个人分别取一些数字,要求第一个人取的任意一个数字与第二个人取的任意一个数字都互质,求方案数(有序)。其中2<=n<=500/)

分析:

选数字与选质因子是等价的,当两个人所选的质因子集合交集为空时,一定构成合法的选数方案。

数据范围为突破口,用二进制表示选择的质因子集合的情况。计数?考虑dp。
2n500
2n500
 

 

Category: 树套树 | Tags: 位运算 动态规划 质数 数论 计数问题 | Read Count: 196

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com