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

ydc的博客

 
 
 

日志

 
 

bzoj 2339(hnoi2011 卡农)  

2013-02-21 22:17:36|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数学题

神数学题

我的数学渣成这样怎么得了咯!!!!!!

 

首先先假设顺序无影响求出答案,最后除以m!

F[i]表示i个片段的方案数

G[i]=A(2^n-1,i)

Two[i]=2^i(其实叫power好听些)

如果我确定了m-1个片段的话,由于是偶数,所以第m个片段就出来了

利用补集转化就是A(2^n-1,m-1)-不合法的

不合法的分两种:

①第m个片段是空集。这就是每个数在m-1都出现了偶数次,那么第m个就是空集了撒,这个方案是F[m-1]

②第m个片段与前面的某一个重复了。我们要这样想,去掉这个重复的方案,有m-2个,这些构成的是合法的。这个方案的位置有i-1个选择,而这个方案的内容有(2^n-1)-(i-2)=2^n-i+1种,综上所述就是F[m-2]*(i-1)*(2^n-i+1)了

所以F[i]=G[i-1]-F[i-1]-F[i-2]*(i-1)*(Two[n]-i+1)

最后F[m]/m!就是答案,由于mod的是质数逆元就可以解决了

然后看似解决了吧……

咦怎么总是超时总是超时啊!!

开始常熟优化!!!

总是超时总是超时!!

看别人时间!!

怎么跑得那么快??????

于是看标程,彻悟了

我是除m!的时候for(int i=1;i<=m;i++)的除!!! m log (mod-2)啊( 快速幂的时间是log(mod-2) )!

标程是先算出O(m)算出m!再O(log(mod-2))算出F[m]/m!

我就是傻逼啊……

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define MAXN 1000010
#define MAXM 1000010
#define MOD 100000007
using namespace std;
typedef long long LL;
int n,m;
LL G[MAXM]={1},F[MAXM],Two[MAXN]={1},ans;
LL power(LL n,LL p)
{
    LL ans=1;
    while(n)
    {
        if(n&1) ans=ans*p%MOD;
        p=p*p%MOD,n>>=1;
    }
    return ans;
}
void Dp()
{
    for(int i=1;i<=n;i++)
        Two[i]=Two[i-1]*2%MOD;
    for(int i=1;i<=m;i++)
        G[i]=G[i-1]*(Two[n]-i)%MOD;
    for(int i=3;i<=m;i++)
        F[i]=(G[i-1]-F[i-1]-F[i-2]*(i-1)%MOD*((Two[n]-i+1+MOD)%MOD)%MOD+2*MOD)%MOD;
    ans=F[m];
    LL jcm=1;
    for(int i=1;i<=m;i++)
        jcm=jcm*i%MOD;
    ans=ans*power(MOD-2,jcm)%MOD;
}
int main()
{
    scanf("%d %d",&n,&m);
    Dp();
    printf("%lld\n",ans);
    return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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