洛谷——P3414 SAC#1 - 组合数
2024-08-25 19:19:27
P3414 SAC#1 - 组合数
题目背景
本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。
寂月城网站是完美信息教室的官网。地址：http://191.101.11.174/mgzd 。
题目描述
辣鸡蒟蒻SOL是一个傻逼，他居然觉得数很萌！
今天他萌上了组合数。现在他很想知道simga(C(n,i))是多少；其中C是组合数（即C(n,i)表示n个物品无顺序选取i个的方案数），i取从0到n所有偶数。
由于答案可能很大，请输出答案对6662333的余数。
输入输出格式
输入格式：
输入仅包含一个整数n。
输出格式：
输出一个整数，即为答案。
输入输出样例
说明
对于20%的数据，n <= 20；
对于50%的数据，n <= 1000；
对于100%的数据，n <= 1 000 000 000 000 000 000 (10^18)
排列组合（卢卡斯定理）能得50分、、
n的范围太大，数组开不开，因此就不能用lus定理了，我们应该在找一种做法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000000
#define mod 6662333
#define ll long long
using namespace std;
int n,ans,jie[N];
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
ll qpow(ll a,ll b,ll p)
{
ll res=;
while(b)
{
) res=res*a%p;
a=a*a%p;b>>=;
}return res;
}
ll C(ll n,ll m,ll p)
{
;
,p)%p;
}
ll Lus(ll n,ll m,ll p)
{
) ;
return Lus(n/p,m/p,p)*C(n%p,m%p,p);
}
int main()
{
n=read();jie[]=;
;i<=n;i++)
jie[i]=1ll*jie[i-]*i%mod;
;i<=n;i+=)
ans=(ans+Lus(n,i,mod))%mod;
printf("%d",ans);
;
}
50分卢卡斯定理
打表找规律
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000000
#define mod 6662333
#define ll long long
using namespace std;
int n,ans,jie[N];
int read()
{
,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
ll qpow(ll a,ll b,ll p)
{
ll res=;
while(b)
{
) res=res*a%p;
a=a*a%p;b>>=;
}return res;
}
ll C(ll n,ll m,ll p)
{
;
,p)%p;
}
ll Lus(ll n,ll m,ll p)
{
) ;
return Lus(n/p,m/p,p)*C(n%p,m%p,p);
}
int main()
{
jie[]=;
;i<;i++)
jie[i]=1ll*jie[i-]*i%mod;
;n<=;n++)
{
ans=;
;i<=n;i+=)
ans=(ans+Lus(n,i,mod))%mod;
printf("%d %d\n",n,ans);
}
;
}
表
我们可以发现，ans=2^(n-1)，因此用快速幂就可以搞定了
n输入的时候要用long long、、（老是RE。。。）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 6662333
#define ll long long
using namespace std;
long long n;int ans;
ll read()
{
ll x=,f=; char ch=getchar();
;ch=getchar();}
+ch-',ch=getchar();
return x*f;
}
int qpow(int a,ll b,int p)
{
;
while(b)
{
) res=1ll*res*a%p;
a=1ll*a*a%p;b>>=;
}return res;
}
int main()
{
n=read();
ans=qpow(,n-,mod);
printf("%d",ans);
;
}
最新文章
- linux下的vim使用教程
- jenkins忘记管理员账号密码的补救方法-转
- 基于HTML5多图片Ajax上传可预览
- Swift - 标签条（UITabBar）标签页控制器（UITabBarController）用法
- 如何升级php版本---从php5.5.12 升级php7.1.5 wamp实践
- python 浅析模块
- canvas练手项目（二）——各种操作基础
- 微信小程序 canvas导出图片模糊
- SQLServer之创建DML AFTER UPDATE触发器
- linux 乌班图 nginx php直接下载下来
- MySql主从搭建详细步骤
- python常见循环练习
- 集合（5）—Map之HashMap()
- MySql之触发器的使用
- 【模板】MST（Kruskal）
- kubernetes架构之二
- Vue基础汇总实践
- .gitignore 无效问题
- 吐泡泡（2018年全国多校算法寒假训练营练习比赛（第二场）+栈模拟）+Plug-in（codeforces81A+栈模拟）
- POJ - 2478