目录
hdu6446Tree and Permutation【邻接表dfs】
hdu6440 Dream【费马小定理】
复习费马小定理的定义：
费马小定理：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。
题意：给你一个素数p，让你定义一个互不相关的乘法表和加法表，使(m+n)^p=m^p+n^p(0≤m,n<p)
题解：
因此，(m+n)^p≡m+n (mod p)， 同时，m^p+n^p≡m+n (mod p) 因此只要把原来的加法表乘法表mod p 就可以了
AC_code:
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
int p;
cin>>p;
for(int i = 0; i < p; i++) {
for(int j = 0; j < p; j++) {
if(j == 0) {
cout<<(i+j)%p;
} else {
cout<<" "<<(i+j)%p;
}
}
cout<<endl;
}
for(int i = 0; i < p; i++) {
for(int j = 0; j < p; j++) {
if(j == 0) {
cout<<i*j%p;
} else {
cout<<" "<<i*j%p;
}
}
cout<<endl;
}
}
return 0;
} hdu6441 Find Integer 【费马大定理】
复习费马大定理的定义：
当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解
题意：
题解：
AC_code:
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
int a, n;
scanf("%d%d", &n, &a);
if(n > 2 || n == 0){
printf("-1 -1\n");
}else if (n == 1){
printf("%d %d\n",1,a+1);
}else {
int b, c;
if(a % 2){
b = (a*a-1)/2;
c = (a*a+1)/2;
printf("%d %d\n",b, c);
}else {
b = (a*a/2-2)/2;
c = (a*a/2+2)/2;
printf("%d %d\n",b, c);
}
}
}
return 0;
} hdu6446Tree and Permutation【邻接表dfs】
题目链接：传送门
题意：给你一颗树，然后让你求n！种序列中，所以得序列和，序列和定义为：A1,A2,A3……AN=A1A2+A2A3+…….An-1An
题解：经过打表推出一种规律，所有任意每两个点之间的距离之和的(n-1)!倍为答案
那么就要求出每两个点之间的距离，暴力走一遍会tle，于是有一种思路：
对于题目给出的n-1条边，我们可以这样考虑，去掉这条边后，将树分成了两部分，一部分有m个节点，另一部分有（n-m）个节点，所以我们必须在这两块中任意选择一个节点才会进过这条边,那么左边的点到右边的点有m*（n-m）条，即这条边贡献了m*（n-m）次，那么我们只要dfs遍历每条边两边的的点，就可以得出最终的答案。
AC_code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const ll mod = 1e9+7;
struct edge{
int u,v;
ll w;
}e[maxn*2];
int head[maxn], num[maxn];
ll node[maxn];
ll ans;
int tot, n;
ll fac[maxn];
void add(int u, int v, int w){
e[++tot].u = head[u];
e[tot].w = w;
e[tot].v = v;
head[u] = tot;
}
void init() {
fac[0] = 1;
fac[1] = 1;
for(int i = 2; i < maxn; i++){
fac[i] = fac[i-1]*i%mod;
}
}
void dfs(int u, int v) {
node[u] = 1;
for(int i = head[u]; i != 0; i = e[i].u){
int to = e[i].v;
if(to == v){
continue;
}
dfs(to, u);
node[u] += node[to];
ans = (ans + (node[to]*(n-node[to])%mod)*e[i].w%mod)%mod;
}
}
int main() {
init();
while(~scanf("%d", &n)){
tot = 0;
memset(head, 0, sizeof(head));
memset(node, 0, sizeof(node));
memset(num, 0, sizeof(num));
for(int i = 1; i < n; i++){
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
num[u]++;
num[v]++;
add(u, v, w);
add(v, u, w);
}
ans = 0;
for(int i = 1; i <= n; i++){
if(num[i] == 1){
dfs(i, 0);
break;
}
}
ans = ans*2%mod*fac[n-1]%mod;
printf("%lld\n",ans);
}
return 0;
} 后续会继续完善题目
京公网安备 11010502036488号