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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2227][Zjoi2011]看电影(movie)  

2014-10-20 08:24:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2227: [Zjoi2011]看电影(movie)

想了好长时间都没想出来怎么做
正解思路好厉害
感觉一般想不到加上去再拆掉这种东西……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
const int N = 1000+10;
int pri[N],n,m,num[N],last[N],used[N],times[N];
short v[N];
void getpri(){
for(int i=2;i<N;i++){
if(!v[i]){
pri[++pri[0]] = i;
last[i] = 1;
used[i] = pri[0];
times[i] = 1;
}
for(int j = 1;j<=pri[0]&&i*pri[j]<N;j++){
v[i*pri[j]] = 1;
if(pri[j] % i==0){
last[i*pri[j]] = last[i];
used[i*pri[j]] = used[i];
times[i*pri[j]] = times[i] + 1;
break;
}else{
last[i*pri[j]] = i;
used[i*pri[j]] = j;
times[i*pri[j]] = 1;
}
}
}
}
void getnum(int nn,int a[],int k){
while(nn > 1){
a[used[nn]] += times[nn]*k;
nn = last[nn];
}
}
const int MLEN = 500;
const int BIT = 10000;
struct BIG{
int d[MLEN];
BIG(){memset(d,0,sizeof(d));d[0] = 1;}
BIG(int a){*this = BIG();if(!a)return;for(d[0] = 0;a;a/=BIT)d[++d[0]] = a%BIT;}
void print(){printf("%d",d[d[0]]);for(int i = d[0]-1;i;i--)printf("%04d",d[i]);}
};
BIG const operator * (const BIG &a,const BIG &b){
BIG c;
c.d[0] = a.d[0] + b.d[0]+1;
for(int i=1;i<=a.d[0];i++)
for(int j=1;j<=b.d[0];j++)
c.d[i+j-1]+=a.d[i]*b.d[j];
for(int i=1;i<=c.d[0];i++)
if(c.d[i] >= BIT){
c.d[i+1] += c.d[i]/BIT;
c.d[i] %= BIT;
}while(c.d[0] > 1&& c.d[c.d[0]] ==0 )c.d[0]--;
return c;
}
typedef BIG Big;
Big pow(Big x,int k){
Big re(1);
for(;k;k/=2,x=x*x)
if(k&1)re=re*x;
return re;
}
Big ans[2];
void getans(){
int i,j;
if(n > m){ans[0] = Big(0);ans[1] = Big(1);return;}
for(i=1;i<=pri[0];i++)num[i] = 0;
getnum(m+1,num,n-1);
getnum(m+1-n,num,1);
getnum(m,num,-n);
ans[0] = ans[1] = Big(1);
for(i=1;i<=pri[0];i++)
if(num[i] > 0){
ans[0] = ans[0]*pow(Big(pri[i]),num[i]);
}else if(num[i] < 0){
ans[1] = ans[1]*pow(Big(pri[i]),-num[i]);
}
}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j;
getpri();
int nn = scan();
while(nn--){
n = scan();m = scan();
getans();
ans[0].print();
printf(" ");
ans[1].print();
printf("\n");
}
return 0;
}

题解:
组合数学。
先加上一个位置并看成一个环,那么方案数就是(k+1)^n,并且可以保证一定合法(因为是环),又因为是环可以转有(k+1)个方案重复了,所以实际上是(k+1)^(n-1)。
拆掉一个空座位回到原问题,那么拆的方案数是(k+1-n)
总方案数是k^n
所以概率是(k+1)^(n-1)*(k+1-n)/(k^n)
需要高精度,因为要化简分数所以直接分解质因数。
似乎是因为gcd(k+1,k)=1,只用考虑gcd(k+1-n,k)所以也可以不分解质因数直接搞
  评论这张
 
阅读(366)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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