#题目链接
#题意简述
有$n(2≤n≤10^9)$种花，每种花一枝，求可组成除了含有$a、b$枝花外共多少种花束。
#简要做法
显然能组成的花束种类最多有$2^n-1$种。那么答案即为$2^n-1-\binom{n}{a}-\binom{n}{b}$。用卢卡斯定理可以快速求解。
#参考代码
|
|
|
using namespace std; |
const ll mod = 1e9 + 7; |
int n, a, b; |
inline ll fpow(int x, int k) { |
ll ret = 1, base = x; |
while(k) { |
if(k & 1) ret = ret * base % mod; |
base = base * base % mod; |
k >>= 1; |
} |
return ret; |
} |
inline ll C(ll n,ll m){ |
if(n < m) return 0; |
if(m > n - m) m = n - m; |
ll a = 1, b = 1; |
for(int i = 0; i < m; ++i) { |
a = (a * (n - i)) % mod; |
b = (b * (i + 1)) % mod; |
} |
return a * fpow(b, mod - 2) % mod; |
} |
inline ll Lucas(ll n, ll m){ |
if(!m) return 1; |
return Lucas(n/mod, m/mod) * C(n%mod,m%mod)%mod; |
} |
const int maxn = 2e5 + 5; |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr), cout.tie(nullptr); |
cin >> n >> a >> b; |
ll ans = fpow(2, n) - 1; |
ans = (ans - Lucas(n, a) - Lucas(n, b)) % mod; |
cout << (ans + mod) % mod << endl; |
return 0; |
} |
#题目链接
#题意简述
一共有$n(3≤n≤2×10^5)$个房间，每个房间中有1个人。每次移动中，一个人可以从所在的房间到达任意一个房间。共有$k(2≤k≤2×10^9)$次移动机会。求最终共有多少种可能的房间情况。
#简要做法
可以枚举共有多少个房间里没有人，这样的房间最少$0$个，最多$min(n-1,k)$个。然后对于有人的房间，用插板法求出可能数量。
#参考代码
|
|
|
using namespace std; |
const ll mod = 1e9 + 7; |
const int maxn = 2e5 + 5; |
int n, k; |
ll f[maxn], finv[maxn]; |
inline ll ksm(int x, int k) { |
ll ret = 1, base = x; |
while(k) { |
if(k & 1) ret = ret * base % mod; |
base = base * base % mod, k >>= 1; |
} |
return ret; |
} |
inline ll C(int n, int m) { |
return f[n] * (finv[n-m] * finv[m] % mod) % mod; |
} |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr), cout.tie(nullptr); |
cin >> n >> k; |
f[0] = f[1] = 1; |
for(int i = 2; i <= n + 1; ++i) f[i] = f[i - 1] * i % mod; |
finv[n + 1] = ksm(f[n + 1], mod - 2); |
for(int i = n; i >= 0; --i) finv[i] = finv[i + 1] * (i + 1) % mod; |
ll ans = 0; |
for(int i = 0; i <= min(n-1, k); ++i) { |
ans = (ans + C(n, i) * C(n-1, n-i-1)) % mod; |
} |
cout << ans << endl; |
return 0; |
} |
F题公式编辑器挂了，先扔一边。。。