GTW likes tree
Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 191 Accepted Submission(s): 38
Problem Description
GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi.
Dis(x,y) is defined as
题解 for E：最后的斗争
E.pdf
带标号边-双联通图计数。
先看这道题的部分分：
对于30%" role="presentation" style="position: relative;">30%30%30\% 的数据，我们写一个dfs，找出所有的N" role="presentation" style="position: relative;">NNN个点的边-双联通图打表即可获得。
仍然是对于30%" role="presentation" style="position: relative;">30%
Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divi
Given a list of integers (A1, A2, ..., An), and a positive integer M, please find the number of positive integers that are not greater than M and dividable by any integer from the given list. Input The input contains several test cases. For each test case, there are two lines. The first line
【题目描述】
求n个点的有向图的强连通图的个数对998244353取模后得结果(无重边，无自环)
定义强连通图为本身为强连通分量的图
【输入格式】
输入一个n表示点数
【输出格式】
输出题目要求的答案
【样例输入】
2
【样例输出】
1
【提示】
对于30%的数据，n<=1000
对于100%的数据，n<=100000
30分的做法详见：网上一篇很好的博客
这个东西是个卷积形式，很容易想到生成函数。
我们来回顾一下两个式子：
f(n)=g(n)+∑k=0n(n−1k−1)f(k)g(n−k) f(n)=g(n)+\sum^{n}_
【题目描述】
求n个点的有向图中强连通图的个数，输出答案对10007取模后得结果(无重边，无自环)
定义强连通图为本身是一个强连通分量的图
【输入格式】
输入一个n表示节点个数
【输出格式】
输出题目要求的答案
【样例输入】
【样例输出】
【提示】
样例解释：
只有一个图，即有边<1,2>和边<2,1>
对于30%的数据，n<=7
对于100%的数据，n<=1000
几个月之前想过强连通图的计数问题，发现根本不可做，暑假集训突然就变成作业了……
这道题的容斥姿势太高超了，功力不够学不来QWQ。
考虑模仿
【题目描述】给出A，B，考虑所有满足l<=a<=A，l<=b<=B，且不存在n>1使得n^2同时整除a和b的有序数,对(a，b),求其lcm(a，b)之和。答案模2^30。 【输入】第一行一个整数T表示数据组数。接下来T行每行两个整数A，B表示一组数据。 T ≤ 2000,A,B ≤ 4 × 10^6 【输出】对每组数据输出一行一个整数表示答案模2^30的值 【输入样例】5
2 2
4 6
3 4
5 1
23333 33333 【输出样例】7
148
48
15
451085813 这道题网上很多题解是化出了一个函数然后快速求这个函数
Rockdu's Blog