先在这里祝大家新年快乐，祝大家在新一年的比赛里"摘金夺银" 此外，再次感谢杭电提供的bestcoder平台，以及何阳的耐心帮助 [title]1001 Harry and Magical Computer[/title] 问题转换成有向图找环问题，可以用dfs深搜。我的写法是，先跑一个floyd，然后看邻接矩阵对角线上是否有1。 [title]1002 Harry And Magic Box[/title] dp题，我们一行一行的考虑。dp[i][j],表示前i行，都满足了每一行至少有一个宝石的条件，而只有j列满足了有宝石的条件的情况有多少种。枚举第i+1行放的宝石数k，这k个当中有t个是放在没有宝石的列上的，那么我们可以得到转移方程： dp[i+1][j+t]+=dp[i][j]*c[m-j][t]*c[j][k-t]，其中c[x][y]，意为在x个不同元素中无序地选出y个元素的所有组合的个数。 [title]1003 Harry and Christmas tree[/title] 我们先考虑单独某种颜色对树上的节点的贡献，假设有x个节点是当前考虑的颜色，那么这x个节点到树根的链都会被贡献1。但是，如果我们一个个的往上统计是不行的，我们给这些点打上标记，意味着这些点到根的链都有1的贡献，最后往上累加上去。但是这些标记会有重复，比如a节点有个1号颜色的标机，b节点也有1号颜色的标记，如果直接往上累加，a跟b的lca以上的部分就是重复累加的，所以要把这部分减掉。假如有这种颜色的节点有k个，我们先对这k个节点按dfs序排序，然后每个节点打上1的标记，然后对第i个有这种颜色的节点u，和对第i-1个有这种色的节点v，求一个lca，假设是w，对w打上一个-1的标记，最后把这些所有的标记往上递推累加，即可得到这种颜色对树上的节点的贡献。那么对于所有的counting，我们只要先按颜色排个序，把相同颜色的放在一起处理，把标记改为累加。最后做一次总的往上递推即可。 排序可以采用基数排序，求lca可以用离线tarjan，这题可以做到复杂度o(n+m)。 [title]1004 Harry and magic string[/title] 先求出p[i],表示以i为回文中心的回文半径，manacher，sa，hash都可以。然后我们考虑以i为回文中心的时候，可以贡献出多少答案。我们先考虑长度为p[i]的那个回文子串，它能贡献的答案，就是末尾在i-p[i]之前的回文子串数，那么长度为p[i-1]的，也是同样的道理。所以我们需要求一个f[x]，表示末尾不超过x的回文子串总共有多少个，把f[i-p[i]]到f[i-1]累加起来即为以i为中心的回文子串能贡献的答案。那我们先统计，以x为结尾的回文子串有多少个，设为g[x]。来看以j为中心的回文子串，它的回文半径是p[j]，那么从j到j+p[j]-1的这一段，都会被贡献一个回文子串，也就是这一段的g[]会被贡献1，这里的处理方法很多，不细说。然后求一次前缀和，即可得到f[x]。

感谢刘老师提供了Bestcoder比赛平台，感谢Herobs在技术上的各种帮助。 [title]1001 Sum Sum Sum[/title] 直接暴力判断素数即可，特殊情况1也是P-number。 [title]1002 Sit sit sit[/title] 设$dp[0][i][j]$表示前i个位置已经确定了被坐的相对次序的合法情况数，并且第i个位置为当中第j个被坐的，第i个位置在第i-1个位置之后被坐。 同理$dp[1][i][j]$表示前i个位置已经确定了被坐的相对次序的合法情况数，并且第i个位置为当中第j个被坐的，第i个位置在第i-1个位置之前被坐。 状态转移方程(当i-1和i+1座位颜色不同时): $dp[0][i][j]=\sum_{k=1}^{j-1}(dp[0][i-1][k]+dp[1][i-1][k])$ $dp[1][i][j]=\sum_{k=j}^{i-1}dp[1][i-1][k]$ 中间边求边处理前缀和即可。 时间复杂度：可以O(n^3)过，也可以处理前缀和优化成O(n^2)。 [title]1003 A Strange Problem[/title] 对于操作二，利用公式 当x >= Phi(C), A^x = A ^ (x%Phi(C) + Phi(C)) (mod C) 对于2333333这个模数来说，求18次欧拉函数后就变成了1，所以只需要保存19层第三次操作的加数即可，然后就直接是线段树区间更新和询问操作了。 Ps:很多人把题目想简单了，操作二不能直接简单的更新，不满足2^(2^x) mod P = 2^( 2^x mod P) mod P。 ```cpp #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <ctime> #include <iostream> using namespace std; typedef __int64 ll; const int MOD = 2333333; const int N = 50000+5; int mo[20] = {2333333,2196720,580608,165888,55296,18432, 6144,2048,1024,512,256,128,64,32,16,8,4,2,1}; int pow2[33]; vector<ll> vt[N]; struct Segtree { #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, r ll mark[N<<2]; int length[N<<2], sum[N<<2]; void build(int rt, int l, int r) { mark[rt] = 0; length[rt] = r-l+1; if(l == r) { vt[l].clear(); int x; scanf("%d", &x); vt[l].push_back(x); sum[rt] = x%MOD; return ; } int mid = l+r>>1; build(lson); build(rson); up(rt); } inline void Add(int &x, int y) { x += y; if(x >= MOD) x -= MOD; } void up(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; Add(sum[rt], 0); } void down(int rt) { if(mark[rt]) { mark[rt<<1] += mark[rt]; mark[rt<<1|1] += mark[rt]; Add(sum[rt<<1], 1LL*length[rt<<1]*mark[rt]%MOD); Add(sum[rt<<1|1], 1LL*length[rt<<1|1]*mark[rt]%MOD); mark[rt] = 0; } } void update(int rt, int l, int r, int L, int R, int v) { if(L <= l && R >= r) { mark[rt] += v; Add(sum[rt], 1LL*length[rt]*v%MOD); return ; } down(rt); int mid = l+r>>1; if(L <= mid) update(lson, L, R, v); if(R > mid) update(rson, L, R, v); up(rt); } int pow_mod(int x, int n, int mod) { int ret = 1%mod; while(n) { if(n&1) ret = 1LL*ret*x%mod; x = 1LL*x*x%mod; n >>= 1; } return ret; } int cal(vector<ll> &v) { if(v.size() < 19) { int pos = v.size()-1; ll ret = v[0]; bool flag = false; if(v[0] >= mo[pos]) { flag = true; ret = ret%mo[pos] + mo[pos]; } pos--; for(int i = 1;i < v.size(); i++) { if(flag) { ret = (pow_mod(2, ret, mo[pos]) +v[i])%mo[pos] + mo[pos]; } else { if(ret >= 30) { flag = true; ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos]+mo[pos]; } else if(pow2[ret] >= mo[pos]) { flag = true; ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos] + mo[pos]; } else { ret = pow2[ret] + v[i]; if(ret >= mo[pos]) { flag = true; ret = ret%mo[pos] + mo[pos]; } } } pos--; } return ret%MOD; } else { ll ret = 1; int pos = 17; bool flag = true; for(int i = v.size()-18;i < v.size(); i++) { ret = (pow_mod(2, ret, mo[pos]) + v[i])%mo[pos] + mo[pos]; pos--; } return ret%MOD; } } void modify(int rt, int l, int r, int x) { if(l == r) { if(mark[rt]) { vt[l][vt[l].size()-1] += mark[rt]; mark[rt] = 0; } vt[l].push_back(0); sum[rt] = cal(vt[l]); return ; } down(rt); int mid = l+r>>1; if(x <= mid) modify(lson, x); else modify(rson, x); up(rt); } int query(int rt, int l, int r, int L, int R) { if(L <= l && R >= r) return sum[rt]; down(rt); int mid = l+r>>1, ret = 0; if(L <= mid) Add(ret, query(lson, L, R)); if(R > mid) Add(ret, query(rson, L, R)); up(rt); return ret; } }tree; int n, m; void init() { for(int i = 0;i <= 30; i++) pow2[i] = 1<<i; } int main() { init(); int op, l, r, x; while(scanf("%d%d", &n, &m) == 2) { tree.build(1, 1, n); while(m--) { scanf("%d", &op); if(op == 1) { scanf("%d%d", &l, &r); printf("%d\n", tree.query(1, 1, n, l, r)); } else if(op == 2) { scanf("%d", &x); tree.modify(1, 1, n, x); } else { scanf("%d%d%d", &l, &r, &x); tree.update(1, 1, n, l, r, x); } } } return 0; } ``` [title]1004 A card problem[/title] 一个莫比乌斯反演的题目。 设$F(d)$为$gcd(B_{i},B_{j})$为d的倍数的pair对，f(d)为$gcd(B_{i},B_{j})=d$的pair对，则$f(d)=\sum_{d|n}F(n)\cdot mu(n/d)$。设$P_{i}$为第i个质数，所以我们要求的就是 $f(1)+f(P_{1})+f(P_{1}^{2})+...+f(P_{2})+f(P_{2}^2)+...$，化简后得 $\sum_{i=1}^{N}F(i)\cdot(mu(1)+\sum_{P_{j}|i}mu(i/P_{j})+\sum_{P_{j}^{2}|i}mu(i/P_{j}^{2})+...)$ 然后就是要计算所有的$F(d)$，对于计算$F(d)$，(i,j)的good pairs有 $F(d)=\frac{A_{i}}{d}\cdot \frac{A_{j}}{d}\cdot \frac{\prod_{k=1}^{N}A_{k}}{A_{i}\cdot A_{j}}(1\leq i< j\leq N)$，然后对于i可以处理出$G(i)=\frac{1}{A_{i}}$，然后对于1~N的G(i)加起来平方下，得到的即为两两间的乘积，然后把自己和自己乘积的减掉再除2可以了，中间的除法运算用逆元，最后是分段来处理即可，时间复杂度为O(nlogn)。计算出F(d)的话也可以直接容斥搞。 ```cpp #include <cstdio> #include <cstring> #include <algorithm> #include <ctime> #include <iostream> using namespace std; const int MOD = (int)1e9+7; const int N = 100000+5; int pri[N], pnum, mu[N], cnt[N], F[N], inv2, a[N], su[N], sum[N], p[N], Inv[N]; bool vis[N]; void mobius(int n) { mu[1] = 1; vis[1] = 1; for(int i = 2;i <= n; i++) { if(!vis[i]) pri[pnum++] = i, mu[i] = -1; for(int j = 0;j < pnum; j++) { if(i*pri[j] > n) break; vis[i*pri[j]] = 1; if(i%pri[j] == 0) { mu[i*pri[j]] = 0; break; } mu[i*pri[j]] = -mu[i]; } } for(int i = 1;i <= n; i++) { if(!vis[i]) p[i] = i; if(!p[i]) continue; if(n/i >= p[i]) p[i*p[i]] = p[i]; for(int j = i;j <= n;j += i) cnt[j] += mu[j/i]; } for(int i = 1;i <= n; i++) cnt[i] += mu[i]; } int pow_mod(int x, int n) { int ret = 1; while(n) { if(n&1) ret = 1LL*ret*x%MOD; x = 1LL*x*x%MOD; n >>= 1; } return ret; } void init(int n) { for(int i = 1;i <= n; i++) Inv[i] = pow_mod(i, MOD-2); inv2 = pow_mod(2, MOD-2); } inline void Add(int &x, int y) { x += y; if(x >= MOD) x -= MOD; if(x < 0) x += MOD; } int main() { mobius(100000); init(100000); int n; while(scanf("%d", &n) == 1) { int mx = 0; for(int i = 1;i <= n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]); for(int i = 1;i <= mx; i++) { su[i] = sum[i] = 0; } int fk = 1; for(int i = 1;i <= n; i++) fk = 1LL*fk*a[i]%MOD; for(int i = 1;i <= n; i++) { int cur = Inv[a[i]]; Add(su[a[i]], 1LL*cur*cur%MOD); Add(sum[1], cur); Add(sum[a[i]+1], -cur); } for(int i = 1;i <= mx; i++) Add(su[i], su[i-1]); for(int i = 1;i <= mx; i++) Add(sum[i], sum[i-1]); for(int i = 1;i <= mx; i++) { int cur = 0, cur2 = 0; for(int j = i;j <= mx; j += i) { Add(cur, sum[j]); int nxt = min(mx, j+i-1); int tmp = 1LL*(j/i)*(j/i)%MOD; Add(cur2, 1LL*tmp*(su[nxt]-su[j-1])%MOD); } cur = 1LL*cur*cur%MOD; F[i] = 1LL*(cur - cur2)*inv2%MOD; if(F[i] < 0) F[i] += MOD; } int ans = 0; for(int i = 1;i <= mx; i++) { Add(ans, 1LL*F[i]*cnt[i]%MOD); } printf("%d\n", 1LL*fk*ans%MOD); } return 0; } ```

[title]1001 Sequence[/title] 判断给定的数列是否满足下标为奇数的和等于下标位偶数的和并且不回文. 分别判断两个性质是否都满足就可以了. 时间复杂度O(n). [title]1002 Sequence II[/title] 要统计四元组的数量我们可以通过枚举c，然后统计区间[1,c-1]有多少二元组(a,b)满足a$<$b且$A_a < A_b$，以及统计出区间[c+1,n]有多少d满足$A_{c} < A_{d}$，根据乘法原理，把这两项乘起来就可以统计到答案里了. 然后我们来处理子问题：区间[1,c-1]内有多少二元组(a,b).那么我们可以枚举b，然后统计区间[1,b-1]内有多少a满足$A_{a} < A_{b}$，那么这个可以通过用树状数组询问前缀和来实现. 时间复杂度是O(nlogn). [title]1003 Cities[/title] 选出K个点$v_{1},v_{2},...v_{K}$使得$\sum_{i=1}^{K}\sum_{j=1}^{K}dis({v}_{i},{v}_{j})$最小. 考虑每条边的贡献，一条边会把树分成两部分，若在其中一部分里选择了x个点，则这条边被统计的次数为x*(K-x)*2. 那么考虑dp[u][i]表示在u的子树中选择了i个点的最小代价，有转移$dp[u][i] = min_{j=0}^{K}(dp[u][i-j]+dp[v][j]+j*(K-j)*2*{w}_{u,v})$，式子中u为v的父亲，${w}_{u,v}$表示(u,v)这条边的长度. 时间复杂度O(nK^2). [title]1004 Sequence III[/title] 对于给定的一个长度t的操作序列，考虑从后往前倒着执行，pop操作变成把一张卡从手中插入到卡牌序列最右端，select操作变成从卡牌序列中任意位置弹出一张牌. 可以发现反过来执行并不会对操作序列产生影响.并且只需要在pop时刻考虑插入卡片是否满足$h_{i}$限制就可以了. 那么搞定了$h_{i}$，剩下的部分就是一个$O({2}^{m}nt)$的状态压缩DP.

[title]1001 NPY and FFT[/title] 这个题直接模拟就行，把数表示成二进制，然后翻转一下，再倒着算出来，就行了 [title]1002 NPY and arithmetic progression[/title] 可以发现等差数列只有（123,234,1234和长度>=3的常数列），如果选择非常数列（123,234,1234）数量大于等于3，可以变为三个或4个常数列,例如（123,123,123）变为（111,222,333）。所以从0-2枚举选择非常数列的数量，再判断能否用常数列覆盖剩下的（如果数字长度正好为0或$\leq 3$就可以）。或者大数就当成20左右的，然后记忆化搜索 [title]1003 NPY and shot[/title] 这是一个高一物理题。扔的距离与投掷角度的函数，符合单峰性质，所以三分角度就行了。 当角度为θ时,设横向速度为vx=cos(θ)*v0,纵向速度为vy=sin(θ)*v0,则扔的距离为: (vy/g+sqrt((vy*vy/(g*2)+h)*2/g))*vx;这个应该手算一下，很容易就能推出来的，具体技巧是将速度延x,y轴分解，然后算一下球的滞空时间，然后乘以横向速度就行。 [title]1004 NPY and girls[/title] 求一个数列的重排方案数可以很容易用排列组合解决。考虑增加一个数对答案的影响：乘了总长度又除以了这个数出现的次数。减少正好相反。所以可以使用莫队算法解决，通过预处理逆元，复杂度为$O(n\sqrt{n})$。 这次比赛的题目很简单,但是英文题目描述确实弄得很糟糕，有的题题意有错误，有的题题意也不好理解， 给大家了一次很糟糕的比赛经历，。作为出题人实在是实在是非常抱歉，希望大家不要因此对Bestcoder产生不好的印象。 另外这次比赛的题目的中文题面会放到Bestcoder官方群里。

[title]1001 CET-6 test[/title] 直接从1到n枚举i，判断n-i是否与1，2，4，7，15相等 复杂度o(n) [title]1002 Formula[/title] 找规律 f(1)=1 f(2)=1*1*2=(1)*(1*2)=1!*2! f(3)=1*1*1*2*2*3=(1)*(1*2)*(1*2*3)=1!*2!*3! 式子可以简化为 $f(n) = \prod\limits_{i=1}^{n}(n!)\%MOD$，直接打表不行，会超内存，可以对数据进行离线处理。排好序之后从小到大暴力。ClogC+10000000 ,C为case数目。 [title]1003 Hun Gui Wei Company[/title] For the queries are relatively many, it requires an efficient data structure to manage these data. My solution is to use segment tree (ST). Before build tree, I sort the staffs according their level in ascending order. In every leaf node of ST, I store one staff in it. In every inner node of ST, I merge the staff in sons of current node according their age in ascending and store them to current node. Thus I can build the ST in time complexity of nlogn. For every query, I find the lower bound and upper bound of level by binary search. Then query sub-segments in ST, for every sub-segment I find the lower bound and upper bound of age by binary search also, then I can get the sum of salary of this sub-segment. One query on ST needs time complexity of logn, binary search in a sub-segment need also time complexity of logn, thus the time complexity of one query is logn*logn. Thus I solve this problem in time complexity of O(nlogn+mlognlogn) and space complexity of O(nlogn). If you have a solution which is more efficient than mine, please tell me. I am very glad to talk with you. [title]1004 LIS again[/title] 题目是要求出有多少个子段的最长上升子序列长度==原序列的最长上升子序列长度 设原序列最长上升子序列长度为LIS 可以发现当以第i元素结尾的最长上升子序列==LIS时，我们使得且这个最长上升子序列第一个元素尽量靠右记为j，那么右端点$\geq i$且左端点$\leq j$的子段的最长上升子序列是==LIS的。 所以我们可以先用统计出第i个元素结尾的最长上升子序列还有这个最长上升子序列的第一个元素最靠右的位置。这一步可以通过线段树来优化，复杂度为O(nlogn) 然后线性从左到右扫描一下枚举子段结尾，统计出合法的子段个数。这一步复杂度是 O(n)