AtCoder Beginner Contest 156
https://atcoder.jp/contests/abc156
D - Bouquet
组合数学。
二项式定理。
注意取模之前一定要保证他是正数(有时候只加一次mod可能不够)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll qmi(ll a, ll k, ll p){
ll res = 1;
while(k){
if(k & 1)
res = (ll)res * a % p;
a = (ll)a * a % p;
k >>= 1;
}
return res;
}
ll C (ll a, ll b) {
ll fz = 1, fm = 1;
for (ll i = 1; i <= b; i++) fm = fm % mod * i % mod;
for (ll i = 0; i < b; i++) fz = fz % mod * (a - i) % mod;
return fz % mod * qmi (fm, mod - 2, mod) % mod;
}
int main () {
ll n, a, b, sum;
cin >> n >> a >> b;
sum = qmi (2, n, mod) - 1 + mod - C(n, a) - C(n, b) + mod;
cout << max(0ll, (sum + mod) % mod);
}
//2^n-1-C(n,a)-C(n,b)
E - Roaming
组合数学。
隔板法。
学习这种转化思想
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
ll fact[N], infact[N];
ll qmi(ll a, ll k, ll p){
ll res = 1;
while(k){
if(k & 1)
res = (ll)res * a % p;
a = (ll)a * a % p;
k >>= 1;
}
return res;
}
ll C (int a, int b) {
if (a < b) return 0;
return fact[a] * infact[b] % mod * infact[a - b] % mod;
}
void init () {
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = (ll)fact[i-1] * i % mod;
infact[i] = (ll)infact[i-1] * qmi(i, mod - 2,mod) % mod;
}
}
int main () {
init ();
ll n, k, sum = 0;
cin >> n >> k;
for (int i = 0; i <= min (k, n - 1); i++) (sum += C(n, i) * C (n - 1, n - i - 1) % mod) %= mod;
cout << sum;
}
//枚举空房子个数i然后隔板法(n个人分到n-i个房子中)
F - Modularness
求相反。
等于:模数相等的 \(d_i\) 的个数
大于:m进制下进位的个数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5005;
int k, q, n, x, m;
ll a[N], d[N], d0[N]; //注意ll
int main () {
cin >> k >> q;
for (int i = 1; i <= k; i++) cin >> d0[i];
while (q--) {
cin >> n >> x >> m;
n --;
ll sum = n, cnt = 0;
for (int i = 1; i <= k; i++) {
d[i] = d0[i] % m;
a[i] = a[i-1] + d[i];
cnt += (d[i] == 0); //相等的个数
}
sum -= n / k * cnt;
for (int i = 1; i <= n % k; i++) sum -= (d[i] == 0);
//计算进位的个数
ll r = x + n / k * a[k] + a[n % k];
sum -= r / m - x / m;
cout << sum << endl;
}
}
- Beginner AtCoder Contest 156beginner atcoder contest 156 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310