Recently, TeaTree acquire new knoledge gcd (Greatest Common Divisor), now she want to test you.
As we know, TeaTree is a tree and her root is node 1, she have n nodes and n-1 edge, for each node i, it has it’s value v[i].
For every two nodes i and j (i is not equal to j), they will tell their Lowest Common Ancestors (LCA) a number : gcd(v[i],v[j]).
For each node, you have to calculate the max number that it heard. some definition:
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes u and v in a tree is the lowest (deepest) node that has both u and v as descendants, where we define each node to be a descendant of itself.
As we know, TeaTree is a tree and her root is node 1, she have n nodes and n-1 edge, for each node i, it has it’s value v[i].
For every two nodes i and j (i is not equal to j), they will tell their Lowest Common Ancestors (LCA) a number : gcd(v[i],v[j]).
For each node, you have to calculate the max number that it heard. some definition:
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes u and v in a tree is the lowest (deepest) node that has both u and v as descendants, where we define each node to be a descendant of itself.
InputOn the first line, there is a positive integer n, which describe the number of nodes.
Next line there are n-1 positive integers f[2] ,f[3], …, f[n], f[i] describe the father of node i on tree.
Next line there are n positive integers v[2] ,v[3], …, v[n], v[i] describe the value of node i.
n<=100000, f[i]<i, v[i]<=100000OutputYour output should include n lines, for i-th line, output the max number that node i heard.
For the nodes who heard nothing, output -1.Sample Input
4 1 1 3 4 1 6 9Sample Output
2 -1 3 -1
题意 ： 给你一颗树，每个结点上面都有一个权值，询问你一任意一个结点作为树根其子树上任意两点的 gcd 的最大值是多少
思路分析 ：
1 . 用 vector 去模拟归并排序，当合并时遇到相同的就记录一下最大值
#define ll long long
const int maxn = 1e5+5;
int n;
vector<int>d[maxn], ve[maxn], f[maxn];
void init(){
for(int i = 1; i <= 100000; i++){
for(int j = i; j <= 100000; j += i){
d[j].push_back(i);
}
}
}
int val[maxn], ans[maxn];
vector<int>temp;
void merge(int x, int y){
temp.clear();
if (f[x].size() == 0) f[x] = d[val[x]];
if (f[y].size() == 0) f[y] = d[val[y]];
int i = 0, j = 0;
while((i < f[x].size()) && (j < f[y].size())){
if (f[x][i] < f[y][j]) temp.push_back(f[x][i]), i++;
else if (f[x][i] > f[y][j]) temp.push_back(f[y][j]), j++;
else {
temp.push_back(f[x][i]);
ans[x] = max(ans[x], f[x][i]); i++, j++;
}
}
while (i < f[x].size()) {
temp.push_back(f[x][i]);
i++;
}
while(j < f[y].size()) {
temp.push_back(f[y][j]);
j++;
}
f[x].clear(); f[y].clear();
f[x] = temp;
}
void dfs(int x){
for(int i = 0; i < ve[x].size(); i++){
int to = ve[x][i];
dfs(to);
merge(x, to);
}
}
int main() {
init();
cin >> n;
int x;
memset(ans, -1, sizeof(ans));
for(int i = 2; i <= n; i++){
scanf("%d", &x);
ve[x].push_back(i);
}
for(int i = 1; i <= n; i++){
scanf("%d", &val[i]);
}
dfs(1);
for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}
2 .
Count the number of cyclic permutations of length n with no continuous subsequence [i, i + 1 mod n].
Output the answer modulo 998244353.
Output the answer modulo 998244353.
InputThe first line of the input contains an integer T , denoting the number of test cases.
In each test case, there is a single integer n in one line, denoting the length of cyclic permutations.
1 ≤ T ≤ 20, 1 ≤ n ≤ 100000OutputFor each test case, output one line contains a single integer, denoting the answer modulo 998244353.Sample Input
3 4 5 6Sample Output
1 8 36
题意 ： 有一个循环全排列，求相邻的位置不存在 [i, i+1] 以及 [n, 1] 的排列的方案数有多少个？
思路分析 ：
好菜啊..学的假的组合数学吧....
首先先说明什么是循环排列：
即把1-n这n个数随意地放到一个圆圈上，循环排列的不同仅仅取决于这n个数的相对位置的不同。
例如1234，2341，3412，4123这些数为相同的循环排列数。
循环排列没有首末之分，这四个元素随便从哪一个元素开始，绕一个方向转过去，都不改变它们的相对顺序；直线排列则首末分明，原来排末位，调换排首位，已改变它们的相对顺序。循环排列与直线排列的主要区别就在这一点上。
从例子看出，直线排列的个数是循环排列个数的n倍
由直线排列个数为n!可推知循环排列个数为(n-1)!。
讲完了循环排列，再来看此题是求不含子串[i,i+1]或[n,1]（以下简称顺序子串，共有n个）的循环排列个数
因为一个排列中可能含有多个顺序子串，所以我们列举至少含有0个，1个，...n个的情况 （注意是至少，因为无法保证恰好含有i个）
包含至少一个顺序子串的循环排列数为C(n,1)*(n-2)!
包含至少两个顺序子串的循环排列数为C(n,2)*(n-3)!
...
包含至少k个顺序子串的循环排列数为C(n,k)*(n-k-1)!
（为什么是(n-k-1)! 当你选出了k个子串之后，至少有k+1个数相对位置已被确定，我们让剩下的(n-k-1)个数全排列即可。）
同时注意到包含n个顺序子串的循环排列数一定是1个。
事件之间相互包含，所以用到容斥原理：
∑(k从0到n-1)(-1)^k*C(n,k)*(n-k-1)!+(-1)^n*1