#2023. 「AHOI / HNOI2017」抛硬币
题目描述
小 A 和小 B 是一对好朋友，他们经常一起愉快的玩耍。最近小 B 沉迷于**师手游，天天刷本，根本无心搞学习。但是已经入坑了几个月，却一次都没有抽到 SSR，让他非常怀疑人生。
勤勉的小 A 为了劝说小 B 早日脱坑，认真学习，决定以抛硬币的形式让小 B 明白他是一个彻彻底底的非洲人，从而对这个游戏绝望。两个人同时抛 bbb 次硬币，如果小 A 的正面朝上的次数大于小 B 正面朝上的次数，则小 A 获胜。
但事实上，小 A 也曾经沉迷过拉拉游戏，而且他一次 UR 也没有抽到过，所以他对于自己的运气也没有太大把握。所以他决定在小 B 没注意的时候作弊，悄悄地多抛几次硬币，当然，为了不让小 B 怀疑，他不会抛太多次。现在小 A 想问你，在多少种可能的情况下，他能够胜过小 B 呢？由于答案可能太大，所以你只需要输出答案在十进制表示下的最后 kkk位即可。
输入格式
有多组数据，对于每组数据输入三个数 a,b,ka, b, ka,b,k，分别代表小 A 抛硬币的次数，小 B 抛硬币的次数，以及最终答案保留多少位整数。
输出格式
对于每组数据，输出一个数，表示最终答案的最后 kkk 位为多少，若不足 kkk 位以 000 补全。
样例
样例输入
2 1 9
3 2 1样例输出
000000004
6样例解释
对于第一组数据，当小 A 抛 222 次硬币，小 B 抛 111 次硬币时，共有 444 种方案使得小 A 正面朝上的次数比小 B 多。
(01,0),(10,0),(11,0),(11,1) (01,0), (10,0), (11,0), (11,1)(01,0),(10,0),(11,0),(11,1)
对于第二组数据，当小 A 抛 333 次硬币，小 B 抛 222 次硬币时,共有 161616 种方案使得小 A 正面朝上的次数比小B多。
(001,00),(010,00),(100,00),(011,00),(101,00),(110,00),(111,00),(011,01)(101,01),(110,01),(111,01),(011,10),(101,10),(110,10),(111,10),(111,11) \begin{aligned} (001,00), (010,00), (100,00), (011,00), (101,00), (110,00), (111,00), (011,01)\\ (101,01), (110,01),(111,01), (011,10), (101,10), (110,10), (111,10), (111,11) \end{aligned}(001,00),(010,00),(100,00),(011,00),(101,00),(110,00),(111,00),(011,01)(101,01),(110,01),(111,01),(011,10),(101,10),(110,10),(111,10),(111,11)
数据范围与提示
对于 10%10\%10% 的数据，a,b≤20a,b\le 20a,b≤20；
对于 30%30\%30% 的数据，a,b≤100a,b\le 100a,b≤100；
对于 70%70\%70% 的数据，a,b≤100000a,b\le 100000a,b≤100000，其中有 20%20\%20% 的数据满足 a=ba=ba=b；
对于 100%100\%100% 的数据，1≤a,b≤1015,b≤a≤b+10000,1≤k≤91\le a,b\le {10}^{15}, b\le a\le b+10000, 1\le k\le 91≤a,b≤1015,b≤a≤b+10000,1≤k≤9，数据组数小于等于 101010。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a,b,k,f[][],mod=,w[];
void prepare(){
f[][]=;
for(int i=;i<=;i++){
f[i][]=f[i][i]=;
for(int j=;j<i;j++)
f[i][j]=(f[i-][j]+f[i-][j-])%mod;
}
}
int main(){
while(scanf("%d%d%d",&a,&b,&k)!=EOF){
mod=;
for(int i=;i<=k;i++)mod*=;
prepare();
int c=max(a,b);
int ans=;
for(int i=;i<=a;i++)
for(int j=;j<i;j++){
ans+=1LL*f[a][i]*f[b][j]%mod;
if(ans>=mod)ans-=mod;
}
int cnt=;
memset(w,,sizeof(w));
while(ans){
w[++cnt]=ans%;
ans/=;
}
for(int i=k;i>=;i--)printf("%d",w[i]);
puts("");
}
return ;
}
30分 暴力组合数
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define INF 1000000001
using namespace std;
ll a,b,K,mod,mod2,mod5,v[][];
ll Pow(ll x,ll y,ll p){
ll res=;
while(y){
if(y&)res=res*x%p;
x=x*x%p;
y>>=;
}
return res;
}
void init(ll k,ll mx){
ll type=(k!=);
v[type][]=;
for(ll i=;i<=mx;i++){
if(i%k)v[type][i]=v[type][i-]*i%mx;
else v[type][i]=v[type][i-];
}
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b)x=,y=;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
ll inv(ll a,ll p){
ll x,y;exgcd(a,p,x,y);
return (x%p+p)%p;
}
ll mul(ll n,ll p,ll pk){
if(!n)return ;
ll res=Pow(v[p!=][pk],n/pk,pk)*v[p!=][n%pk]%pk;
return res*mul(n/p,p,pk)%pk;
}
ll C(ll n,ll m,ll p,ll pk,ll fg){
if(n<m)return ;
ll cnt=;
for(ll i=n;i;i/=p)cnt+=i/p;
for(ll i=m;i;i/=p)cnt-=i/p;
for(ll i=(n-m);i;i/=p)cnt-=i/p;
if(p==&&fg)cnt--;
if(cnt>=K)return ;
ll s1=mul(n,p,pk),s2=mul(m,p,pk),s3=mul(n-m,p,pk);
ll res=Pow(p,cnt,pk)*s1%pk*inv(s2,pk)%pk*inv(s3,pk)%pk;
if(p==&&fg)res=res*inv(,pk)%pk;
return res*(mod/pk)%mod*inv(mod/pk,pk)%mod;
}
ll Lucas(ll n,ll m,ll fg){
return (C(n,m,,mod2,fg)+C(n,m,,mod5,fg))%mod;
}
int main(){
init(,);init(,);
while(cin>>a>>b>>K){
mod2=Pow(,K,INF);mod5=Pow(,K,INF);mod=Pow(,K,INF);
ll ans=Pow(,a+b-,mod);
if(a==b)ans=(ans-Lucas(a+b,a,)+mod)%mod;
else {
for(ll i=(a+b)/+;i<a;i++)ans=(ans+Lucas(a+b,i,))%mod;
if(!((a+b)%))ans=(ans+Lucas(a+b,(a+b)/,))%mod;
}
while(ans<mod/)mod/=,printf("");
printf("%lld\n",ans);
}
return ;
}
100分 exLucas