原题：Product it again 原题大意给出N，M，让你求出GCD(1, 1) GCD(1, 2) … GCD(1, M) GCD(2, 1) GCD(2, 2) … GCD(2, M) … GCD(N, 1) GCD(N, 2) … GCD(N, M) 结果mod10^9+7。 算法分析考虑某一个质数p对答案的贡献ans。ans = p^((n/p m/p) + ((n/p^2 m/p^2)) + ….)原理类比n!的质因子分解后，对某个质因子p的指数大小的计数。所以我们只需要一个线性筛即可，然后暴力计数。复杂度约为O((n/logn) logn logn)。这里有关于n！质因子分解和素数快速筛法的相关博客： http://www.doc88.com/p-9159772516121.html http://blog.csdn.net/qq_31917799/article/details/51612654 http://blog.csdn.net/dinosoft/article/details/5829550 程序代码#include &l ...

原题：小Hi的烦恼 原题大意描述小Hi从小的一大兴趣爱好就是学习，但是他发现尽管他认真学习，依旧有学神考的比他好。 小Hi在高中期间参加了市里的期末考试，一共五门：语文、数学、英语、物理、化学。 成绩出来之后，小Hi发现有些同学，所有科目都考的比他好，他很烦恼。所以他想知道所有科目都比自己名次靠前的同学的人数。 为了方便，可以认为不存在两个人某一门名次是相同的。 其他同学们也想知道有多少人全面碾压了他们，所以你需要对所有人输出答案。 输入第一行，一个正整数N(N <= 30000)，表示人数。 接下来N行，每行五个整数，分别表示五门课依次的排名。 输出输出共N行，每行一个整数，表示答案。 样例输入4 1 1 2 2 1 2 3 3 3 2 3 2 1 1 3 4 4 4 4 4 样例输出0 1 0 3 算法分析这一题主要是bitset的运用，算法题目已经给出了提示： 小Ho：我想用集合的角度去考虑这个问题。对于每一维，比如说X维，我们能通过按X维的坐标排序，不难求出对i点来说X维比i点小的所有点的集合。现在的问题就转化成对点i来说，求出X维，Y维，Z维，Q维，W维分别比i所在那一 ...

原题：World is Exploding 原题大意给出一个长度为n的整数序列V，要求输出有多少个四元组{a,b,c,d}。满足1 <=a < b <= n,1 <=c < d <= n,a!=b!=c!=d 且 VaVd 算法分析先用树状数组处理每个位置(离散化处理，否则10^9存不下)左边比它大或小的有几个，右边比它大或小的有几个，算出这个序列分正序数和逆序数，并乘起来，然后去掉a==c,a==d,b==d,b==d,四种情况的个数。 程序代码#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; ll num,a[50005],zx[50005],zd[50005],yx[50005],yd[50005],C[50005],b[50005]; ll lowbit(ll x){ r ...

原题：Jam’s problem again 原题大意给出n个坐标(x,y,z)，如果有两个点(xi,yi,zi) 和 (xj,yj,zj)满足 xi≥xj，yi≥yj，zi≥zj，那么i这个点的等级就加一,最后输出每个点的等级。 算法分析三维偏序，模板题，CDQ分治加树状数组，最后注意处理两个点完全相同的情况。 程序代码#include <cstdio> #include <algorithm> #include <cstring> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 100000+100; const int N = 100010; struct po{ int x, y, z, id; }a[maxn],b[maxn]; int ans[maxn]; int C[maxn*2]; int T, n; bool cmp1(po a, po b){ if(a.x != b.x) return a.x < b. ...

原题：Infinite Sequence 原题大意给定n，有多少个长度为无穷的数列{a}满足： 对于n < k，ak = an 对于i < j < k <= i + ai，aj = ak 1 <= ai <= n，n <= 10^6，对10^9 + 7取摸 算法分析 http://blog.csdn.net/crzbulabula/article/details/70145999 其中第二种情况的第三点k较大时，就是说如果(1+k)长度超过n时，后位只能补一，相当于给第二种情况的第一点里，k>i-3时的补充。 程序代码#include <cstdio> #include <cstring> using namespace std; const int mod = 1e9+7; const int maxn = 1e6+5; typedef long long ll; int f[maxn]; int up(int a,int b){ a+=b; if(a>=mod) a-=mod; ...