清北学堂第一套试题
算
【问题背景】 zhx 帮他妹子做数学题。
【问题描述】
求
如 ,这个值为 。
【输入格式】 仅一行,包含两个数 和 . 【输出格式】 仅一行,包含所求的答案 mod 的值。 【样例输入】
3 3
【样例输出】
56
【数据范围与规定】 对于的数据,所有。 对于的数据,所有
题解:
观察公式,可以发现最后求和的值为
因此,我们就可以枚举 ,计算 ,容易发现这就是个等比数列。
根据等比数列前 向求和公式可得到:
其中 为首项, 为项数, 为公比,且 。
因为要除以 后对 取模,因此要利用逆元。
逆元:
在数论中,如果 ,我们就说 和 在模 意义下互为乘法逆元,记作 。
为了解决模意义下的除法问题,我们引入了逆元。
其实可以看做模 意义下的 。那么在模 意义下, 就可以变形为
费马小定理求逆元:
费马小定理:若 是质数,且 则有
由于模数是个质数,所以 ,所以有 ,
至此,题目就做完了。
#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和他的妹子去一个国家旅游,共有个旅游景点,条双向连接的道 路将它们联通起来,每一条道路有固定长度。一开始zhx位于号景点。 现在希望你能够求出旅行长度最小的方案,使得每个景点至少被访问到一次。
【输入格式】
第一行两个整数,代表景点数目。 接下来行,每行三个整数表示有一条从s到t的双向道路,长度为。和的编号从开始。
【输出格式】
3
1 2 3
2 3 3
【样例输出】
6
【样例输入】
3
1 2 3
1 3 3
【样例输出】
9
【数据规模与约定】
对于的数据,。
对于的数据,。 对于的数据,。
一行一个整数,代表能够访问每个景点至少一次的方案的最小旅行长度。
题解:
由于一共有 个点, 条边,便能够组成一棵树。
如图,每个点都要向上下下走,因此我们只要用所有边的权值之和减去最长边的就行了。
#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;
}