感觉还是好多东西记不得了，gg。
A – 收历史作业
傻逼二维偏序，开场8分钟就切了（为什么暑假没有这种送分题？）
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 200;
int n, m, k, nodes[MAX_N], upper;
vector<int> mp;
struct point
{
int x, y, c;
bool operator<(const point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y) || (x == rhs.x && y == rhs.y && c > rhs.c); }
} pts[MAX_N];
int ripe(int x) { return lower_bound(mp.begin(), mp.end(), x) - mp.begin() + 1; }
inline int lowbit(int x) { return x & (-x); }
void update(int x, int d)
{
for (; x <= upper; x += lowbit(x))
nodes[x] = max(nodes[x], d);
}
int query(int x, int ret = 0)
{
for (; x; x -= lowbit(x))
ret = max(ret, nodes[x]);
return ret;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++)
{
scanf("%d%d%d", &pts[i].x, &pts[i].y, &pts[i].c);
mp.push_back(pts[i].x), mp.push_back(pts[i].y);
}
pts[++k] = point{n - 1, m - 1, -1}, mp.push_back(n - 1), mp.push_back(m - 1);
sort(mp.begin(), mp.end()), mp.erase(unique(mp.begin(), mp.end()), mp.end());
upper = mp.size();
for (int i = 1; i <= k; i++)
pts[i].x = ripe(pts[i].x), pts[i].y = ripe(pts[i].y);
sort(pts + 1, pts + 1 + k);
int ans = 0;
for (int i = 1; i <= k; i++)
{
int dp = query(pts[i].y) + pts[i].c;
if (pts[i].c == -1)
ans = ++dp;
update(pts[i].y, dp);
}
printf("%d\n", ans);
return 0;
}
B – 发奖金
观察之后发现答案非常显然，为\(n + m \choose m\)。观察模数发现有\(60%\)的 Lucas 可以做，然后就做不下去了（纯属因为不记得 CRT 怎么写了）。
首先\(80%\)的分很好写，直接在两个模域下用 Lucas 算，然后用 CRT 合并即可。其实正解差不多也这样，多次 Lucas 再合并。但是正解有一个特别的地方，就是存在\(c_i \geq 1\)。这样就没法直接用乘法逆元算。但是，我们发现乘法逆元存在的情况，当且仅当两数之间互质。那么，我们可以在算逆元的时候把\(p_i\)提出来，然后让互质部分用 exgcd 进行求逆元的操作。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, m, p, primes[MAX_N], cnt[MAX_N], ptot, cmod, pic[MAX_N], ai[MAX_N];
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y), t = x;
x = y, y = t - (a / b) * y;
return d;
}
int getInv(int a)
{
int x, y;
exgcd(a, cmod, x, y);
return (x + cmod) % cmod;
}
int quick_pow(int bas, int tim)
{
if (tim < 0)
return quick_pow(getInv(bas), -tim);
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % cmod;
bas = 1LL * bas * bas % cmod;
tim >>= 1;
}
return ret;
}
int fac(int x, int mod)
{
int ret = 1;
for (int i = 1; i <= x; i++)
if (i % mod != 0)
ret = 1LL * ret * i % cmod;
return ret;
}
int fac(int x, int mod, int &tot)
{
// lucas;
if (x < mod)
return fac(x, mod);
int seg = x / cmod, rem = x % cmod;
int res = 1LL * quick_pow(fac(cmod - 1, mod), seg) * fac(rem, mod) % cmod;
tot += x / mod;
res = 1LL * res * fac(x / mod, mod, tot) % cmod;
return res;
}
int binomial(int n_, int k_, int mod)
{
int a = 0, b = 0, c = 0, res = 1;
res = 1LL * res * fac(n_, mod, a) % cmod * getInv(fac(k_, mod, b)) % cmod * getInv(fac(n_ - k_, mod, c)) % cmod;
return 1LL * res * quick_pow(mod, a - (b + c)) % cmod;
}
void factorize(int tmp)
{
for (int i = 2; 1LL * i * i <= tmp; i++)
if (tmp % i == 0)
{
primes[++ptot] = i;
while (tmp % i == 0)
cnt[ptot]++, tmp /= i;
}
if (tmp > 1)
primes[++ptot] = tmp, cnt[ptot] = 1;
}
int main()
{
scanf("%d%d%d", &n, &m, &p), n += m;
factorize(p);
for (int i = 1; i <= ptot; i++)
{
cmod = 0x7fffffff, cmod = pic[i] = quick_pow(primes[i], cnt[i]);
ai[i] = binomial(n, m, primes[i]);
}
cmod = 0x7fffffff;
// begins to merge;
for (int i = 2; i <= ptot; i++)
{
int x, y;
exgcd(pic[i - 1], pic[i], x, y);
pic[i] *= pic[i - 1];
ai[i] = ((1LL * x * (ai[i] - ai[i - 1]) * pic[i - 1] % pic[i] + ai[i - 1]) % pic[i] + pic[i]) % pic[i];
}
printf("%d\n", ai[ptot]);
return 0;
}
C – 大水题
大毒瘤
看得出来是数位 DP，但是根本写不动。答案肯定是：
\[ \text{ans} = m – \frac{\text{回文数} \leq m \text{的数的个数} – \text{回文数等于自身的个数}}{2} \]
那么我们可以考虑设置状态\(dp[i][0/1][0/1]\)，代表到第\(i\)位是否与\(m\)相等、是否与\(m\)的回文数相等。那么，小于\(m\)的个数显然是\(dp[len][0][0]+dp[len][1][0]\)。回文数等于自身的个数无疑就只用满足前半部分小于即可，也就是\(dp[len >> 1][0][0] + dp[len >> 1][0][1] + dp[len >> 1][1][0]\)。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1010, mod = 1e9 + 7;
int n, len, m, digits[MAX_N * MAX_N], dp[MAX_N * MAX_N][2][2];
char str[MAX_N * MAX_N];
int quick_pow(int bas, int tim)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % mod;
bas = 1LL * bas * bas % mod;
tim >>= 1;
}
return ret;
}
const int inv2 = quick_pow(2, mod - 2);
int main()
{
scanf("%d%s", &n, str + 1), len = n * n;
for (int i = 1; i <= len; i++)
digits[i] = str[i] - '0', m = (1LL * m * 10 % mod + digits[i]) % mod;
int last_digit;
dp[0][1][0] = 1;
for (int i = 0; i <= len - 1; i++)
for (int bit = 0; bit <= 1; bit++)
{
last_digit = bit ? digits[i + 1] : 9;
for (int k = 0; k <= last_digit; k++)
{
dp[i + 1][bit && (k == last_digit)][(k <= digits[len - i]) ? 0 : 1] =
(dp[i + 1][bit && (k == last_digit)][(k <= digits[len - i]) ? 0 : 1] + dp[i][bit][0]) % mod;
dp[i + 1][bit && (k == last_digit)][(k < digits[len - i]) ? 0 : 1] =
(dp[i + 1][bit && (k == last_digit)][(k < digits[len - i]) ? 0 : 1] + dp[i][bit][1]) % mod;
}
}
int firstTerm = (0LL + dp[len][0][0] + dp[len][1][0]) % mod;
int secondTerm = (0LL + dp[len >> 1][0][0] + dp[len >> 1][0][1] + dp[len >> 1][1][0]) % mod;
int ans = (0LL + m + mod - 1LL * (firstTerm + mod - secondTerm) % mod * inv2 % mod) % mod;
printf("%d\n", ans);
return 0;
}