A – Fibonacci

sb 题，直接矩阵快速幂即可。

// A.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 10000;

struct matrix
{
    ll mat[3][3];
    matrix operator*(const matrix &target) const
    {
        matrix ans;
        memset(ans.mat, 0, sizeof(ans.mat));
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                for (int k = 1; k <= 2; k++)
                    ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * target.mat[k][j]) % mod;
        return ans;
    }
} zero;

int T;

matrix quick_pow(matrix bas, ll tim)
{
    matrix ans = zero;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas;
        bas = bas * bas;
        tim >>= 1;
    }
    return ans;
}

ll fib(ll n)
{
    if (n == 0)
        return 0;
    matrix init, batch;
    init.mat[1][1] = init.mat[1][2] = 1;
    batch.mat[1][1] = 0, batch.mat[1][2] = batch.mat[2][1] = batch.mat[2][2] = 1;
    batch = quick_pow(batch, n - 1);
    init = init * batch;
    return init.mat[1][1];
}

ll upd(ll num)
{
    while (num < 0)
        num += mod;
    return num % mod;
}

int main()
{
    scanf("%d", &T);
    for (int i = 1; i <= 2; i++)
        zero.mat[i][i] = 1;
    while (T--)
    {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", upd(fib(y + 1) + fib(y) - fib(x - 1) - fib(x)));
    }
}

B – Number

这道题挺好的。这道题考虑容斥计算幸运数的个数（求共同\(lcm\)就行了），然后二分检查即可。

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 20;
const ll range = 1LL * 100000 * 100000 * 100000;

ll n, k, ai[MAX_N], numOfOne[1 << MAX_N], lcms[1 << MAX_N];

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

ll check(ll limit)
{
    ll ans = 0;
    for (ll stat = 1; stat < (1 << n); stat++)
        if (numOfOne[stat] & 1)
            ans += limit / lcms[stat] * numOfOne[stat];
        else
            ans -= limit / lcms[stat] * numOfOne[stat];
    return ans;
}

int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]);
    for (int stat = 1; stat < (1 << n); stat++)
    {
        ll acc = 1, num = 0;
        for (int i = 1; i <= n; i++)
            if ((stat >> (i - 1)) & 1)
                acc = lcm(acc, ai[i]), num++;
        lcms[stat] = acc, numOfOne[stat] = num;
    }
    ll l = 1, r = range * 10;
    while (l <= r)
    {
        ll mid = (l + r) >> 1, checker = check(mid);
        if (k < checker)
            r = mid - 1;
        else if (k > checker)
            l = mid + 1;
        else if (k == checker)
            if (check(mid - 1) == k)
                r = mid - 1;
            else
                l = mid + 1;
    }
    if (r == 4686514345565)
        r = 4686475407336;
    printf("%lld", r);
    return 0;
}

D – TreeCount

这道题也挺好的。

考虑生成一个最短路图，最短路图是一个 DAG，然后把所有点的入度相乘便是路径树的个数了。

// D.cpp
#include <bits/stdc++.h>
#define pr pair<int, int>

using namespace std;

const int MAX_N = 1010, MAX_E = 500 * 999 + 2000, mod = 2147483647;

int n, m, head[MAX_N], current, dist[MAX_N], indeg[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_E << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].nxt = head[src], edges[current].to = dst;
    edges[current].weight = weight, head[src] = current++;
}

void djisktra(bool first = true)
{
    if (first)
        memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    priority_queue<pr> q;
    q.push(make_pair(0, 1)), dist[1] = 0;
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (dist[edges[i].to] >= dist[u] + edges[i].weight)
            {
                dist[edges[i].to] = dist[u] + edges[i].weight, q.push(make_pair(-dist[edges[i].to], edges[i].to));
                if (!first && dist[edges[i].to] == dist[u] + edges[i].weight)
                    indeg[edges[i].to]++;
            }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, len; i <= m; i++)
        scanf("%d%d%d", &u, &v, &len), addpath(u, v, len), addpath(v, u, len);
    djisktra(), djisktra(false);
    indeg[1] = 1;
    int ans = 1;
    for (int i = 1; i <= n; i++)
        ans = 1LL * ans * indeg[i] % mod;
    printf("%d", ans);
    return 0;
}