注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2339】【HNOI2011】【卡农】  

2014-04-08 15:56:28|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题目大意:有n个元素,m次可以从n个元素中选出一些组成一个序列,要求任意两次选出的元素组成的集合都不相同,要求每个元素总的被选择的次数为偶数,求满足上面两个限制的方案数(m次不分先后的)。
     (n,m<=10^6)
     这题咱承认咱不会做= =,原来至少还有点思路...

     唯一的思路就是,应该是先满足偶数这个条件,即先枚举每个元素选了多少次,然后咱们考虑将这些元素分成m份,每一份都不相同的方案数。后者感觉有点像斯特林数的即视感...不过光考虑枚举前者的那个偶数的条件实际上就已经要超时了....然后就去看题解了。
    
     1)首先第一点,这一点咱没有想到,那就是 假设咱们知道了前m-1个集合,那么第m个集合的内容就很容易通过奇偶性算出来的。(注意每一个元素的个数要求是偶数)
     2)然后第二点,咱们可以注意到总的集合的种类有 2^n-1种(除去了空集),这是第二点,咱们需要记住。
     3)这里由 2)咱们可以发现,实际上这个问题就是从 2^n-1种集合中选出m-1个互不相同的,并且要求推出来的第m个和前m-1个集合不相同。求这样的方案数。
     4)为了方便计算,咱们就规定一个顺序,即两种取法虽然取的集合是一样的,但是假设它们顺序不同就被判定为不同。这样子算出的答案咱们要除以 m!
     5)咱们设 f[i] 表示的是从n个元素选出i个不相同集合的方案数(要求是偶数)。咱们就考虑转移。
          咱们再设 g[i] 表示的就是选出 i 个不相同的集合并排列起来(不要求),显然这个是有g[i]=A(2^n-1,i)
          记得咱们的 3)的结论么?实际上咱们只需要求出选出不同的m-1个集合,就可以推出第m个集合了。咱们考虑g[m-1]的所有方案实际上都可以推出一个第m的方案,那么接下来怎么做?g[m-1]的话实际上存在一些不合法的方案,咱们需要去掉这些方案。
          首先第一个不合法的地方在于 g[m-1]中的一些方案,它们的所有元素和都是偶数,这个的个数是f[m-1]的,咱们发现这些方案会导致第m个集合是空集,这是不允许的,得减去。
          然后第二个,就是有可能 第 m个集合和原来的m-1个集合有重复。咱们来算算这些的个数,咱们实际上可以把那个重复的删掉,然后把第m个插入到这m-2个集合中。
          stop!!这里咱们可以思考的更深一点... 咱们来考虑一下为什么会重复..实际上就是那m-2个元素造成了所有的元素的个数都是偶数!然后加上了这个要重复的集合之后最后只能再添加进来一个相同的。也就是说,这个m-2个集合的可能性有f[m-2]种,每一种都会产生重复集合,然后重复集合可以插入到m-1个位置中,然后重复集合可以取2^n-1-(m-2)种,所以就是 f[m-2]*(m-1)*(2^n-m+1)
        即最后的转移就是 f[m]=g[m-1]-f[m-1]-f[m-2]*(m-1)*(2^n-m+1)
        咱们发现咱们并没有给m什么特殊的限制,咱们可以一般化。
        即 f[i]=g[i-1]-f[i-1]-f[i-2]*(i-1)*(2^n-i+1)
        然后递推下去就可以了,f[n]就是答案*m!。 
        求出来之后注意还要除以 m!,这个的话咱们可以求乘法逆元得到。

        然后关于乘法逆元,有 x*x^-1≡1(mod modd),咱们发现实际上当如果有 y≡x(mod modd)的话,那么y的逆元也是 x^-1,所以咱们用 m!mod 10^9+7做逆元即可。

        另外此题的 mod 为 100000007,话说有谁像咱一样傻叉的将它一开始看做10^9+7了....其实这个是10^8+7...
        这里咱们再来讲讲初始化,f[1]=0是显然的,因为总有元素的个数为奇数,同理f[2]=0也是显然的,要使元素的个数为偶数必须是两个相同的集合。
==================================

program bzoj2339;
const maxn=1000010;
      modd=100000007;
var f,g:array[0..maxn]of int64;
    two,n,m,key,oil,ans:int64;

procedure exgcd(a,b:int64;var x,y:int64);
var s,t:int64;
begin
  if b=0 then
   begin
     x:=1;y:=0;
     exit;
   end;
  exgcd(b,a mod b,s,t);
  x:=t;
  y:=s-t*(a div b);
end;

procedure init;
var i:longint;
begin
  read(n,m);
  two:=1;key:=1;
  for i:=1 to n do
   begin
    two:=two*2;
    if two>modd then two:=two mod modd;
   end;
  for i:=1 to m do
   begin
    key:=key*i;
    if key>modd then key:=key mod modd;
   end;
  exgcd(key,modd,key,oil);
  if key<0 then key:=key+((-key)div modd+1)*modd;
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  f[0]:=0;
  g[0]:=1;
  f[1]:=0;
  f[2]:=0;
  g[2]:=((two-1)*(two-2))mod modd;
  for i:=3 to m do
   begin
     f[i]:=g[i-1]-f[i-1]-((f[i-2]*(i-1))mod modd)*(two-i+1);
     if f[i]<0 then f[i]:=f[i]+((-f[i]) div modd+1)*modd;
     if f[i]>modd then f[i]:=f[i] mod modd;
     g[i]:=g[i-1]*(two-i);
     if g[i]>modd then g[i]:=g[i] mod modd;
   end;
  ans:=(f[m]*key)mod modd;
  write(ans);
end;

begin
  init;
end.

          
  评论这张
 
阅读(43)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017