清北学堂第一套试题

【问题背景】 zhx 帮他妹子做数学题。

【问题描述】

\sum_{x=1}^{N}\sum_{y=1}^Mx^y

N=3, M=3 ,这个值为 1^1+1^2+1^3+2^1+2^2+2^3+3^1+3^2+3^3=56

【输入格式】 仅一行,包含两个数 N M . 【输出格式】 仅一行,包含所求的答案 mod 10^9 + 7 的值。 【样例输入】

3 3

【样例输出】

56

【数据范围与规定】 对于 50\% 的数据,所有 1 ≤ N,M ≤ 10 。 对于 100\% 的数据,所有 1 ≤ N,M ≤ 50000

题解:

观察公式,可以发现最后求和的值为 1^1+1^2+1^3+...+1^{m-1}+1^m+2^1+2^2+2^3+...+2^{m-1}+2^m+...+n^1+n^2+n^3+...+n^{m-1}+n^m

因此,我们就可以枚举 i ,计算 i^1+i^2+i^3+...+i^{m-1}+i^m ,容易发现这就是个等比数列。

根据等比数列前 n 向求和公式可得到:

S_n = \frac{a(r^n-1)}{r-1}

其中 a 为首项, n 为项数, r 为公比,且 r\ne1

因为要除以 r-1 后对 10^9+7 取模,因此要利用逆元。

逆元:

在数论中,如果 ab\equiv1\pmod{p} ,我们就说 a b 在模 p 意义下互为乘法逆元,记作 a=\text{inv}(b)

为了解决模意义下的除法问题,我们引入了逆元。

\text{inv}(a) 其实可以看做模 p 意义下的 \frac{1}{a} 。那么在模 p 意义下, \frac{a}{b} 就可以变形为 a\cdot \text{inv}(b) \pmod{p}

费马小定理求逆元:

费马小定理:若 p 是质数,且 \gcd(a, p) = 1 则有 a^{p-1}\equiv1\pmod{p}

由于模数是个质数,所以 \gcd(a, p)=1 ,所以有 \text{inv}(a) = a^{-1} \text{inv}(a)\equiv a^{p-2}\pmod{p}

至此,题目就做完了。

#include <cstdio>
#define MOD 1000000007
long long pow(long long b, long long p) {
    long long ans = 1;
    while(p > 0) {
        if (p % 2 == 1)
            ans = (ans * b) % MOD;
        b = (b * b) % MOD;
        p = p >> 1;
    }
    return ans % MOD;
}
long long inv(long long k) {
    return pow(k, MOD - 2);
}
int main() {
    long long p, q;
    scanf("%lld %lld", &p, &q);
    long long ans = q;
    for (long long i = 2; i <= p; i++) {
        long long n = q, a = i, r = i, sum = 0; //参考等比数列
        sum = a * (pow(r, n) - 1 + MOD) % MOD;
        sum = (sum * inv(r - 1) + MOD) % MOD; //逆元
        ans = (ans + sum + MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

【问题背景】 zhx 和他的妹子出去玩。

【问题描述】

zhx和他的妹子去一个国家旅游,共有 N 个旅游景点, N-1 条双向连接的道 路将它们联通起来,每一条道路有固定长度。一开始zhx位于 1 号景点。 现在希望你能够求出旅行长度最小的方案,使得每个景点至少被访问到一次。

【输入格式】

第一行两个整数 N ,代表景点数目。 接下来 N-1 行,每行三个整数 s,t,w 表示有一条从s到t的双向道路,长度为 w s t 的编号从 1 开始。

【输出格式】

3 
1 2 3 
2 3 3 

【样例输出】

6

【样例输入】

3 
1 2 3 
1 3 3

【样例输出】

9

【数据规模与约定】

对于 30\% 的数据, 1≤N≤10

对于 70\% 的数据, 1 ≤ N ≤ 1000 。 对于 100\% 的数据, 1≤N≤50000,1≤w≤1000

一行一个整数,代表能够访问每个景点至少一次的方案的最小旅行长度。

题解:

由于一共有 n 个点, n-1 条边,便能够组成一棵树。

如图,每个点都要向上下下走,因此我们只要用所有边的权值之和减去最长边的就行了。

#include <queue>
#include <cstdio>
#include <cstring>
#define MAXN 50001
int n, m, s = 1;
int head[MAXN], dis[MAXN], vis[MAXN], cnt;
struct edge {
    int to, dis, next;
} e[MAXN * 2];
void add_edge(int u, int v, int w) {
    cnt++;
    e[cnt].to = v;
    e[cnt].dis = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
struct node {
    int dis, pos;
    bool operator < (const node &x) const {
        return x.dis < dis;
    }
};
std::priority_queue<node> q;
void Dijkstra() {
    dis[s] = 0;
    q.push((node){0, s});
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos;
        if (vis[x] != 0) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            if (dis[y] > dis[x] + e[i].dis) {
                dis[y] = dis[x] + e[i].dis;
                if (vis[y] == 0) q.push((node){dis[y], y});
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    m = n - 1;
    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
        ans += 2 * w;
    }
    memset(dis, 0x3f, sizeof(dis));
    Dijkstra();
    int maxx = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > maxx) maxx = dis[i];
    printf("%lld\n", ans - maxx);
    return 0;
}