标签 - 杂OJ

? 解题记录 ? ? 杂OJ ? ? 二次剩余 ?    2018-12-19 19:15:49    368    0    0
The number x is called a square root of a modulo n (root( a, n)) if x* x = a (mod n). Write the program to find the square root of number a by given modulo n. Input One number K in the first line is an amount of tests ( K ≤ 100000). Each next line represents separate test, which contains inte
? 解题记录 ? ? 杂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。 考虑模仿
? 解题记录 ? ? 杂OJ ? ? cdq分治 ?    2018-07-13 23:28:09    802    0    0
【题目描述】给定一个有n个元素的序列,元素编号为1~n,每个元素有三个属性a,b,c,求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。 【输入格式】第一行一个整数n,表示序列长度。 第二行n个整数,分别表示a1~an。 第三行n个整数,分别表示b1~bn。 第四行n个整数,分别表示c1~cn。 【输出格式】一个整数,表示答案。 【样例输入】5 1 5 3 4 2 2 5 3 4 1 1 2 5 3 4【样例输出】3【样例解释】满足条件的(i,j)共有以下三对: (1,2) (1,3) (1,4) 【数据范围与约定】对于30%的数据,n<
? 解题记录 ? ? 杂OJ ? ? 堆 ?    2018-05-15 21:51:18    626    1    1
描述给定一个长度为 n 的非负整数序列 a[1..n]。 你每次可以花费 1 的代价给某个 a[i] 加1或者减1。 求最少需要多少代价能将这个序列变成一个不上升序列。 输入第一行一个正整数 n。 接下来 n 行每行一个非负整数,第 i 行表示 a[i]。 1 ≤ n ≤ 500000 0 < a[i] ≤ 109 输出一个非负整数,表示答案。 样例解释[5,3,4,5] -> [5,4,4,4] 样例输入 4 5 3 4 5样例输出 2​&nbs
? 解题记录 ? ? 单调队列 ? ? 动态规划 ? ? 杂OJ ?    2018-03-24 15:03:16    782    0    0
题目描述输入一个长度为n的整数序列,从中找出一段不超过M的连续子序列,使得整个序列的和最大。例如 1,-3,5,1,-2,3当m=4时,S=5+1-2+3=7当m=2或m=3时,S=5+1=6 输入格式第一行两个数n,m第二行有n个数,要求在n个数找到最大子序和 输出格式一个数,数出他们的最大子序和 提示数据范围:100%满足n,m<=300000 样例数据输入样例 #1输出样例 #16 4 1 -3 5 1 -2 37本题我们要找一个不超过M长度的和最大的子段(可以不取)。那么直接把所有前缀和求出来,For一遍每一个右端点,用单调队列维护一下前面m个以内最小的前缀和是多少就
? 解题记录 ? ? 杂OJ ? ? 回文自动机 ?    2018-03-10 09:11:00    578    0    0
【题目描述】对于给定的字符串S,我们想知道它有多少个不同的回文子串。 【输入】一行,一个长度不超过100000的仅小写字母构成的字符串。 【输出】一个整数,代表不同的回文子串个数。 【输入样例】abcd 【输出样例】4 【提示】有20%的数据,输入字符串的长度不超过1000。 本题有后缀数组的O(n log n)算法,但是既然咱们有回文自动机不是板子题就轻松切掉了嘛。于是又水了一题…… #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int
? 解题记录 ? ? 杂OJ ? ? 亚线性筛 ?    2018-01-23 11:27:17    439    0    0
给出一个数N,输出小于等于N的所有数,两两之间的最大公约数之和。 相当于计算这段程序(程序中的gcd(i,j)表示i与j的最大公约数): 由于结果很大,输出Mod 1000000007的结果。 G=0;for(i=1;i<N;i++)for(j=1;j<=N;j++){ G = (G + gcd(i,j)) % 1000000007;} Input 输入一个数N。(2 <= N <= 10^10) Output 输出G Mod 1000000007的结果。 Input示例 100 Output示例 31080 推导: &am
? 解题记录 ? ? 杂OJ ? ? 亚线性筛 ?    2018-01-19 13:12:12    835    0    0
出一个数N,输出小于等于N的所有数,两两之间的最小公倍数之和。 相当于计算这段程序(程序中的lcm(i,j)表示i与j的最小公倍数): 由于结果很大,输出Mod 1000000007的结果。 G=0;for(i=1;i< N;i++)for(j=1;j<=N;j++){ G = (G + lcm(i,j)) % 1000000007;} Input 输入一个数N。(2 <= N <= 10^10) Output 输出G Mod 1000000007的结果。 Input示例 4 Output示例 72 推导: G(