[Fortuna OJ]Jan 9 – Group A 解题报告

感觉还是好多东西记不得了,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;
}

 


发表评论

邮箱地址不会被公开。 必填项已用*标注