hdu_4869(费马小定理+快速幂)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4869
Turn the pokers
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2001 Accepted Submission(s): 707
Each test case begins with a line containing two non-negative integers n and m(0<n,m<=100000).
The next line contains n integers Xi(0<=Xi<=m).
3 2 3
3 3
3 2 3
3
For the second example:
0 express face down,1 express face up
Initial state 000
The first result:000->111->001->110
The second result:000->111->100->011
The third result:000->111->010->101
So, there are three kinds of results(110,011,101)
LL quickmod(LL a,LL b)
{
LL ans = ;
if(b==) return ans;
if(b&) ans = (ans*a)%mod;
return ans = (quickmod(a,b/))%mod;
})%mod;
为了降低复杂度。我们现在展开这个递归式子,写一个非递归的程序:
1.如果b是偶数,我们可以记k = a2 mod c,那么求(k)b/2 mod c就可以了。
2.如果b是奇数,我们也可以记k = a2 mod c,那么求
((k)b/2 mod c × a ) mod c =((k)b/2 mod c * a) mod c 就可以了。
上述过程最后一定是b先等于1再等于0,故b=0时候结束程序
下面是模板代码:
LL quickmod(LL a,LL b)
{
LL ans = ;
while(b)
{
if(b&) ans = (ans*a)%mod;
a = (a*a)%mod;
b>>=;
}
return ans;
}
下面介绍一下费马小定理:
a^(p-1) = 1(mod p) p是素数
一般应用有:
A: a^b mod p 在b很大的时候可以先用b = b % (p-1)
B: 在阶乘中减去除法的操作。a^(p-2) = 1/a(mod p)
这个题就应用了B
下面是这个题的ac代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
const LL mod = ;
const int N = ; LL f[N]; void init()
{
int i;
f[] = ;
for(i = ; i < N; i++)
f[i] = (f[i-]*i)%mod;
} LL quickmod(LL a, LL b)
{
LL ans = ;
while(b)
{
if(b&){
ans = (ans*a)%mod;
}
b>>=;
a = (a*a)%mod;
}
return ans;
} int main()
{
int n,m,i,j,k,l,r,x,ll,rr;//ll保存最小的1的个数
//l表示上一次的最小的1的个数,rr保存的是最多的1的个数
//r表示的是上一次的最多的1的个数
init();
while(~scanf("%d%d",&n,&m))
{
l = r = ;
for( i = ; i < n; i++)
{
scanf("%d",&x);
if(l>=x) ll = l - x;
else if(r>=x) ll = ((l%)==(x%))?:;
else ll = x-r; if(r+x<=m) rr = r+x;
else if(l+x<=m) rr = (((l+x)%)==(m%)?m:m-);
else rr = *m-(l+x); l = ll;
r = rr;
}
LL sum = ;
for(i = l; i<=r; i+=)
sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-)%mod))%mod;
printf("%I64d\n",sum%mod);
}
return ;
}
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mod 1000000009
#define LL __int64
#define maxn 100000+5 LL f[maxn]; void set()
{
int i;
f[] = ;
for(i = ; i<maxn; i++)
f[i] = (f[i-]*i)%mod;
} LL quickmod(LL a,LL b)
{
LL ans = ;
while(b)
{
if(b&)
{
ans = (ans*a)%mod;
b--;
}
b/=;
a = ((a%mod)*(a%mod))%mod;
}
return ans;
} int main()
{
int n,m,i,j,k,l,r,x,ll,rr;
set();
while(~scanf("%d%d",&n,&m))
{
l = r = ;
for(i = ; i<n; i++)
{
scanf("%d",&x);
//计算最小的1的个数,尽可能多的让1->0
if(l>=x) ll = l-x;//当最小的1个数大于x,把x个1全部翻转
else if(r>=x) ll = ((l%)==(x%))?:;//当l<x<=r,由于无论怎么翻,其奇偶性必定相等,所以看l的奇偶性与x是否相同,相同那么知道最小必定变为0,否则变为1
else ll = x-r;//当x>r,那么在把1全部变为0的同时,还有x-r个0变为1
//计算最大的1的个数,尽可能多的让0->1
if(r+x<=m) rr = r+x;//当r+x<=m的情况下,全部变为1
else if(l+x<=m) rr = (((l+x)%) == (m%)?m:m-);//在r+x>m但是l+x<=m的情况下,也是判断奇偶,同态那么必定在中间有一种能全部变为1,否则至少有一张必定为0
else rr = *m-(l+x);//在l+x>m的情况下,等于我首先把m个1变为了0,那么我还要翻(l+x-m)张,所以最终得到m-(l+x-m)个1 l = ll,r = rr;
}
LL sum = ;
for(i = l; i<=r; i+=)//使用费马小定理和快速幂的方法求和
sum+=((f[m]%mod)*(quickmod((f[i]*f[m-i])%mod,mod-)%mod))%mod;
printf("%I64d\n",sum%mod);
} return ;
}
最新文章
- bzoj2599: [IOI2011]Race(点分治)
- 用c语言编写直接插入法
- uvalive 4589 Asteroids
- mysql中的存储过程和事务隔离
- tomcat 端口被占用
- Mina学习之IoHandler
- [转载]Nginx 反向代理、负载均衡、页面缓存、URL重写及读写分离详解
- Linux文件上传工具下载工具及详细使用说明
- java中this和super关键字的使用
- vue-cli@2的原理解析
- nginx概述
- Chrome插件-网页版BusHound
- android延时弹出软键盘
- [转]c++优先队列(priority_queue)用法详解
- Linux命令_用户身份切换
- unusedjs
- 三公网络监督平台APP上线,源代码出售。
- python匹配两个字符串中间的字符串
- POJ 2196
- 【BZOJ】4530: [Bjoi2014]大融合
热门文章
- 开启tomcat的apr模式,并利用redis做tomcat7的session的共享。
- 《Create Your own PHP Framework》笔记
- Effective Java 第三版——15. 使类和成员的可访问性最小化
- 房上的猫:switch选择结构,与选择结构总结
- 解决adb push时出现的";Read-only file system";问题
- 在VSCode中编辑HTML文档时,在Dom标签上写style属性时智能提示的问题
- hadoop的安装和配置(二)伪分布模式
- HTTP首部解析
- C# ASP.NET 转换为int型的方法 很实用
- [转载]Tortoise SVN使用方法,简易图解