CF768F. Barrels and boxes
Solution
又一道据说是套路题。
核心在于枚举
W
W
W的连续段个数为
x
x
x。 然后就能知道
F
F
F的连续段个数为
x
−
1
,
x
,
x
+
1
x-1,x,x+1
x−1,x,x+1，可以用插板法求出任意把
W
W
W分
x
x
x段的方案数，分
x
x
x段每段
W
W
W至少
H
H
H个的方案数，以及任意把
F
F
F分
x
−
1
,
x
,
x
+
1
x-1,x,x+1
x−1,x,x+1段的方案数了。
（注意一些边界情况）
Code
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
using namespace std
;
template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }
typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;
const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=1e9+7;
const int MAXN
=600005;
const int INF
=0x3f3f3f3f;
inline int read()
{
int f
=1,x
=0; char c
=getchar();
while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }
while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }
return x
*f
;
}
int n
,fac
[MAXN
],inv
[MAXN
];
int quick_pow(int x
,int y
)
{
int ret
=1;
for (;y
;y
>>=1)
{
if (y
&1) ret
=1ll*ret
*x
%mods
;
x
=1ll*x
*x
%mods
;
}
return ret
;
}
void Init(int n
)
{
fac
[0]=1;
for (int i
=1;i
<=n
;i
++) fac
[i
]=1ll*fac
[i
-1]*i
%mods
;
inv
[n
]=quick_pow(fac
[n
],mods
-2);
for (int i
=n
-1;i
>=0;i
--) inv
[i
]=1ll*inv
[i
+1]*(i
+1)%mods
;
}
ll
C(int x
,int y
) { if (x
<y
||y
<0) return 0; return 1ll*fac
[x
]*inv
[y
]%mods
*inv
[x
-y
]%mods
; }
int upd(int x
,int y
) { return x
+y
>=mods
?x
+y
-mods
:x
+y
; }
signed main()
{
int f
=read(),w
=read(),h
=read(),ans1
=0,ans2
=0;
if (!f
) { puts(w
<=h
?"0":"1"); return 0; }
if (!w
) { puts("1"); return 0; }
Init(f
+w
);
for (int i
=1;i
<=w
;i
++) ans1
=upd(ans1
,C(w
-1,i
-1)*(C(f
-1,i
-2)+C(f
-1,i
-1)+C(f
-1,i
-1)+C(f
-1,i
))%mods
);
for (int i
=1;i
<=w
&&w
-h
*i
-1>=0;i
++) ans2
=upd(ans2
,C(w
-h
*i
-1,i
-1)*(C(f
-1,i
-2)+C(f
-1,i
-1)+C(f
-1,i
-1)+C(f
-1,i
))%mods
);
printf("%lld\n",1ll*ans2
*quick_pow(ans1
,mods
-2)%mods
);
return 0;
}
