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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 3398 String  

2013-09-03 08:30:41|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=3398
求由n个1 m个0组成的,并且任意前缀中1的个数不少于0的个数的字符串的个数,结果对20100510取余。
参考了下大牛的做法,思路很好:http://blog.csdn.net/abcjennifer/article/details/5922270

①:我们设初始在坐标系的原点(0,0),从字符串第一位开始,碰到一个0就向上走,碰到一个1就向右走,那么由n个1、m个0组成的字符串最后必定走到(n,m)点,即满足由n个1、m个0组成的字符串的个数为C(n+m,n) = C(n+m,m) (满足n+m长度内n个长度走1或者m个长度走0)。
②:对于任意前缀中1的个数不少于0的个数的字符串的个数这个条件,可以看成是坐标系中,从(0,0)点走到(m, n)点,并且跟y=x-1这条直线不相交的方案数。又因为(0,0)点关于直线y=x-1的对称点是(1,-1),而从(1,-1)点走到(m, n)点的所有方案一定都会与直线y=x-1相交,对于这些方案,将从(1,-1)点到与y=x-1的第一个交点之间的路径关于y=x-1对称翻转过去,就可以得到所有不满足题意的从(0,0)点走到(m, n)点的方案,于是最终答案就是C(n+m, n)-C(n+m,n+1)。
 
化简公式得到:C(n+m,n)-C(m+n,m-1) = (m+n)!*(n+1-m) / ((n+1)! * m!)
接下来就是求上式子模20100501的值,因为n、m很大,所以我们利用质因数分解来分解阶乘,然后分子分母抵消指数最后求指数幂的和即可,但是这样做还是会TLE。而用对于阶乘,有很多非常好的性质可以利用(不利用就TLE。。。),下面介绍N!的质因数分解,也就是求N!中x的幂,首先因为N! = 1*2*3*……*N,所以N!中x的幂就是各个数质因数分解后x的幂之和,考虑含1,2,……,N中含x^1的共有x^1,2*x^1,……,y*x^1共y个,其中y=floor(N/x^1),而含x^2的共有x^2,2*x^2,……,y*x^2共y个,其中y=floor(N/x^2)=floor((N/x)/x),所以可以利用递归来计算N!中x的幂。

/*
* pro.cpp
*
* Created on: 2013-09-03
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
//#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=2000010;
const int M=150010;
const int MOD=20100501;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

int k,p[M]; //p数组记录各个素数的幂
bool f[N];
int n,m,tot,len,prime[M];

//打印素数表
void fun()
{
int i,j,s;
memset(f,true,sizeof(f));
f[1]=false;
tot=0;
prime[tot++]=2;
for(i=4;i<=N;i+=2)
f[i]=false;
for(i=3;i*i<=N;i+=2)
{
if(!f[i])
continue;
prime[tot++]=i;
for(s=2*i,j=i*i;j<=N;j+=s)
f[j]=false;
}
for(;i<=N;i++)
if(f[i])
prime[tot++]=i;
}

//对某个数分解质因数
void fun1(int t)
{
for(int i=0;t>1;i++)
{
if(t%prime[i] == 0)
{
int s=0;
while(t%prime[i] == 0)
{
s++;
t/=prime[i];
}
p[i]+=s;
}
}
}

//对某个数的阶乘分解质因数
void fun2(int t,int temp)
{
int tmp,i;
for(i=0;i<tot && prime[i]<=t;i++)
{
tmp=t;
while(tmp)
{
if(temp == 0)
p[i]+=tmp/prime[i];
else
p[i]-=tmp/prime[i];
tmp/=prime[i];
}
}
len=max(len,i);
}

//快速幂取余
LL mod_exp(LL a,LL b,LL c)
{
LL ans=1;
while(b)
{
if(b & 1)
ans=ans*a%c;
a=a*a%c;
b/=2;
}
return ans;
}

LL Get()
{
LL tmp,ans=1;
for(int i=0;i<len;i++)
{
tmp=mod_exp((LL)prime[i],(LL)p[i],MOD);
ans=ans*tmp%MOD;
}
return ans;
}

void solve()
{
len=-1;MEM(p);
fun1(n+1-m);
fun2(n+m,0);
fun2(n+1,1);
fun2(m,1);
printf("%I64d\n",Get());
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
fun();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
solve();
}
return 0;
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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