T1 变换
一道DP题,用 \(f_{i, j, 0/1}\) 来表示到了第 \(i\) 个数,总共修改了 \(j\) 次,前面的数是/不是山谷点,做 DP 即可。
赛事想到前面是不是山谷点的情况但是直接忽略力(悲)
#include <fstream>
using namespace std;
using ll = long long;
const ll kMaxN = 1e5 + 1, kMod = 1e9 + 7;
ifstream cin("alternate.in");
ofstream cout("alternate.out");
ll n, a[kMaxN], jie[kMaxN];
ll fpow(ll a, ll b) {
ll res = 1;
while (b) {
(b & 1) && (res = res * a % kMod);
b >>= 1;
a = a * a % kMod;
}
return res;
}
ll C(ll m, ll n) {
return jie[m] * fpow(jie[m - n], kMod - 2) % kMod * fpow(jie[n], kMod - 2) % kMod;
}
int main() {
jie[0] = 1;
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i], jie[i] = jie[i - 1] * i % kMod;
}
ll ans = 0;
if (n & 1) {
for (int i = 1; i <= n; i += 2) {
ans = (ans + C(n / 2, i / 2) * fpow(-1, i / 2) * a[i] % kMod) % kMod;
}
} else {
ll ans2 = 0;
for (int i = 1; i < n; i += 2) {
ans = (ans + C(n / 2 - 1, i / 2) * fpow(-1, i / 2) * a[i] % kMod) % kMod;
}
for (int i = 2; i <= n; i += 2) {
ans2 = (ans2 + C(n / 2 - 1, i / 2 - 1) * fpow(-1, i / 2 - 1) * a[i] % kMod) % kMod;
}
ans += ans2;
}
cout << (ans % kMod + kMod) % kMod << '\n';
return 0;
}
T2 交替
根据超大眼观察法,我们可以发现,当剩余数组大小为偶数的时候,呈现一个组合数的形式,于是使用公式 \(C_{m}^{n} = \dfrac{m!}{n!(m-n)!}\) 配合逆元求出组合数来得出。
代码难度有点高,花了25min才调出来。
#include <fstream>
using namespace std;
using ll = long long;
const ll kMaxN = 1e5 + 1, kMod = 1e9 + 7;
ifstream cin("alternate.in");
ofstream cout("alternate.out");
ll n, a[kMaxN], jie[kMaxN];
ll fpow(ll a, ll b) { // 快速幂
ll res = 1;
while (b) {
(b & 1) && (res = res * a % kMod);
b >>= 1;
a = a * a % kMod;
}
return res;
}
ll C(ll m, ll n) { // 逆元求组合数
return jie[m] * fpow(jie[m - n], kMod - 2) % kMod * fpow(jie[n], kMod - 2) % kMod;
}
int main() {
jie[0] = 1;
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i], jie[i] = jie[i - 1] * i % kMod;
}
ll ans = 0;
if (n & 1) { // 奇数的情况
for (int i = 1; i <= n; i += 2) {
ans = (ans + C(n / 2, i / 2) * fpow(-1, i / 2) * a[i] % kMod) % kMod;
}
} else { // 偶数的情况
ll ans2 = 0;
for (int i = 1; i < n; i += 2) {
ans = (ans + C(n / 2 - 1, i / 2) * fpow(-1, i / 2) * a[i] % kMod) % kMod;
}
for (int i = 2; i <= n; i += 2) {
ans2 = (ans2 + C(n / 2 - 1, i / 2 - 1) * fpow(-1, i / 2 - 1) * a[i] % kMod) % kMod;
}
ans += ans2;
}
cout << (ans % kMod + kMod) % kMod << '\n';
return 0;
}
T3 拳击
赛事不会。
没有回复内容