首页 > 代码库 > BNU 4307 Set Problem 组合数学
BNU 4307 Set Problem 组合数学
链接:http://acm.bnu.edu.cn/v3/problem_show.php?pid=4307
竟然是一道往年北师新生赛热身赛的题目。
题意:要从【0,n-1】组成的集合中找到,包括两个连续数(n-1,0也可以)的子集的个数。
思路:用aa记录题目所求,用bb记录【0,n-1】中不包括(n-1,0)以外的其他满足题目条件的子集数。用递推的方法计算。
计算bb[i]时,包括三种情况,1.不选择i-1的子集数bb[i-1];2.选择i-1但不选择i-2的子集数bb[i-2];3.既选择i-1又选择i-2的子集数Pow[i-2]。
计算aa[i]时,包括四种情况,1.不选择i-1的子集数bb[i-1];2.选择i-1同时选择i-2的子集数bb[i-2];3.既选择i-1又选择0的子集数bb[i-2];(前两种情况应该用容斥原理减去i-2,i-1,0同时选择的情况)4.选择i-1却不选择i-2和0的情况。
代码:
#include <iostream> #include <cstdio> using namespace std; #define MOD 8061 int aa[1000005],bb[1000005],Pow[1000005]; void init() { Pow[0]=1; for(int i=1;i<=1000000;i++) Pow[i]=(Pow[i-1]*2)%MOD; bb[2]=1; bb[3]=3; aa[2]=1; aa[3]=4; for(int i=4;i<=1000000;i++) { bb[i]=(bb[i-2]+bb[i-1]+Pow[i-2]+MOD)%MOD; aa[i]=(bb[i-1]+Pow[i-2]*2-Pow[i-3]+bb[i-3]+MOD)%MOD; } } int main() { int a; init(); while(~scanf("%d",&a)) { printf("%d\n",aa[a]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。