HNOI2017抛硬币

题面

主体思路

首先我们发现有2a+b2^{a+b}中硬币情况,在大部分的情况下把每个硬币翻转以后,结果反转。

但是就是有一些特例。

当a=b时,答案形如2a+bF2\frac{2^{a+b}-F}{2},其中F表示小A小B抛出来的硬币数相等的情况数,此时反转前后小A都没赢。

于是我们列出式子:

F=i=0n(ai)2=i=0n(ai)(aai)=(2aa)F=\sum_{i=0}^n\binom{a}{i}^2=\sum_{i=0}^n\binom{a}{i}\binom{a}{a-i}=\binom{2a}{a}

当a>b时,答案形如2a+b+G2\frac{2^{a+b}+G}{2},其中G表示翻转前后小A都赢的情况数,注意前面相等的情况翻转后结果也会反转,所以不需要减 那么设小A有X个正面,小B有Y个,显然X>YX>YaX>bYa-X>b-Y,所以0<XY<ab0<X-Y<a-b

这样我们又可以列出式子:

G=i=0bj=1ab1(bi)(ai+j)=i=1ab1j=0b(bj)(ai+j)=i=1ab1j=0b(bbj)(ai+j)=i=1ab1(a+bi+b)G=\sum_{i=0}^b\sum_{j=1}^{a-b-1}\binom{b}{i}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\sum_{j=0}^b\binom{b}{j}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\sum_{j=0}^b\binom{b}{b-j}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\binom{a+b}{i+b}

然后我们就可以计算出答案×2\times 22×10k2\times 10^k取膜的值,然后÷2。

复杂度优化

如果直接写,会T成70分。

然后我们需要加上一些优化:

优化1:(每组询问中)由于CRT合并的始终是那两个数,所以可以先计算一次两个数相对对方的逆元,然后可以直接用,于是优化掉了CRT的log2nlog_2 n,然而发现并没有什么用。

优化2:(全局) 由于一直是mod 2^(k+1)和mod 5^k求逆元,我们可以先记录a2[i]表示1..i中不是2倍数的数的积 ,a5[i]表示1..i中不是5倍数的数的积 。然后可以直接用,优化力度较大,并且我们还可以把递归搞成非递归强行加速。

然而还是只有70pts。

优化3:(真正的骚操作)我们发现除了k=2的特例,a2[2k]=1a2[2^k]=1。并且在1..5^9范围内,a5[5k]=1a5[5^k]=-1,然后又可以把快速幂干掉。

然后在不开氧气优化的本机80pts,开O2AC,在洛谷也AC(有O2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/*
Author: CNYALI_LK
LANG: C++
PROG: coin.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
void Write(ll a,ll n){
if(n>1)Write(a/10,n-1);
putchar(a%10+'0');
}

ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;else if(c==EOF)exit(0);
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
ll Pow(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=c*a;
a=a*a;
b>>=1;
}
return c;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;
return a;
}
else{
ll d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
}
ll inv(ll a,ll p){
ll x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
ll t2a,t5a;
ll fpm(ll a,ll b,ll p){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll mxa,F2,F5;
ll CRT(ll a,ll b){
// printf("%lld %lld !!\n",a,b);
return (a*F5%mxa*t5a+b*F2%mxa*t2a)%mxa;
}
ll js(ll a,ll p){
if(a>=p)return a/p+js(a/p,p);
return 0;
}
ll a2[102424],a5[2333333];
ll fac2(ll a){
ll ans=1,g;
while(a){
ans=ans*a2[a%t2a]%t2a;
a/=2;
}
return ans;
}
ll k;
ll lucas2(ll a,ll b){
ll sa=fac2(a),sb=inv(fac2(b),t2a),sc=inv(fac2(a-b),t2a);
ll ga=js(a,2),gb=js(b,2),gc=js(a-b,2);
ga-=gb+gc;
return sa*sb%t2a*sc%Pow(2,max(k+1-ga,0LL))*Pow(2,ga);
}
ll fac5(ll a){
ll ans=1;
while(a){
ans=ans*a5[a%t5a]%t5a;
if((a/t5a)&1)ans=t5a-ans;
a/=5;
}
return ans;
}
ll lucas5(ll a,ll b){
ll sa=fac5(a),sb=inv(fac5(b),t5a),sc=inv(fac5(a-b),t5a);
ll ga=js(a,5),gb=js(b,5),gc=js(a-b,5);
ga-=gb+gc;
return sa*sb%t5a*sc%Pow(5,max(k-ga,0LL))*Pow(5,ga);
}
int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
ll a,b;
a2[0]=a5[0]=1;
for(int i=1;i<=1024;++i){
a2[i]=a2[i-1];
if(i&1)a2[i]=a2[i]*i%1024;
}
for(int i=1;i<=1024;i<<=1)printf("%lld\n",(a2[i]-1)%i);
for(int i=1;i<=1953125;++i){
a5[i]=a5[i-1];
if(i%5)a5[i]=a5[i]*i%1953125;
}
printf("G");
for(int i=1;i<=1953125;i*=5)printf("%lld\n",(a5[i]+1)%i);
// printf("%lld %lld\n",a2[1024],a5[1953125]);
while(1){
a=read();b=read();k=read();
mxa=Pow(10,k)*2;
t2a=Pow(2,k+1),t5a=Pow(5,k);
exgcd(t2a,t5a,F2,F5);
F2=(F2%t5a+t5a)%t5a;
F5=(F5%t2a+t2a)%t2a;
ll ans=fpm(2,a+b,mxa);
if(a==b)ans+=mxa-CRT(lucas2(a+a,a),lucas5(a+a,a));
else{
for(ll i=1;i<a-b;++i)ans+=CRT(lucas2(a+b,b+i),lucas5(a+b,b+i));
}
ans%=mxa;
ans/=2;
Write(ans,k);
putchar('\n');
}
return 0;
}
文章目录
  1. 1. 主体思路
  2. 2. 复杂度优化
|

博客使用Disqus作为评论系统