标签 - 容斥

? 解题记录 ? ? HDU ? ? 容斥 ? ? 莫比乌斯函数 ?    2019-03-15 15:47:54    534    0    0
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
? 解题记录 ? ? 洛谷 ? ? 动态规划 ? ? 组合数 ? ? 容斥 ?    2018-10-06 17:42:53    570    0    0
题解 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%
? 解题记录 ? ? 容斥 ? ? HDU ?    2018-08-21 11:19:44    593    0    0
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
? 解题记录 ? ? 杂OJ ? ? 容斥 ?    2018-08-21 11:01:23    570    0    0
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
? 解题记录 ? ? 杂OJ ? ? 容斥 ? ? 组合数 ? ? 生成函数 ? ? FFT|NTT ?    2018-08-15 09:58:01    936    0    0
【题目描述】 求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}_
? 解题记录 ? ? 杂OJ ? ? 容斥 ? ? 动态规划 ? ? 组合数 ?    2018-08-15 08:56:05    1336    0    1
【题目描述】 求n个点的有向图中强连通图的个数,输出答案对10007取模后得结果(无重边,无自环) 定义强连通图为本身是一个强连通分量的图 【输入格式】 输入一个n表示节点个数 【输出格式】 输出题目要求的答案 【样例输入】 【样例输出】 【提示】 样例解释: 只有一个图,即有边<1,2>和边<2,1> 对于30%的数据,n<=7 对于100%的数据,n<=1000 几个月之前想过强连通图的计数问题,发现根本不可做,暑假集训突然就变成作业了…… 这道题的容斥姿势太高超了,功力不够学不来QWQ。 考虑模仿
? 解题记录 ? ? BZOJ ? ? 莫比乌斯函数 ? ? 容斥 ?    2018-08-13 11:42:45    572    0    0
【题目描述】给出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​   这道题网上很多题解是化出了一个函数然后快速求这个函数