[title]A: Ferries Wheel[/title] 题意：有$N$个人去做摩天轮，每个人进一个缆车，问有多少人满足：【(他的缆车的值+左边车的值)%INT_MAX=右边缆车的值】. 解法：暴力，记录每个缆车出现的次数，排序去重，枚举缆车的值，判断是否满足那个等式即可。 HACK点：题目没告诉你输入是有重复数的(开始没有样例3，担心被喷得太惨，就加了样例3），只有一个缆车的情况不一定只是$N=1$. [title]B: Misaki's Kiss again[/title] 题意：找出$0$到$N-1$中，有哪些数满足$gcd(N,M)==N xor M$. 解法：暴力枚举$N$的所有约数$K$，令$M=N xor K$,再判断$gcd(N,M)$是不是等于$K$。时间$O(sqrt(N))$; HACK点：有些人可能会一不小心枚举的时候定义成了int.导致$i*i$成负数。 [title]C：The Experience of Love[/title] 题意：给一棵树，求任意｛两点路径上的最大边权值-最小边权值｝的总和。 解法：$sigma(maxVal[i]-minVal[i])=sigma(maxVal)-sigma(minVal)$;所以我们分别求所有两点路径上的最大值的和，还有最小值的和。再相减就可以了。求最大值的和的方法用带权并查集，把边按权值从小到大排序，一条边一条边的算，当我们算第$i$条边的时候权值为$wi$,两点是$ui,vi$,前面加入的边权值一定是小于等于当前$wi$的，假设与$ui$连通的点有$a$个，与$vi$连通的点有$b$个，那么在$a$个中选一个，在$b$个中选一个，这两个点的路径上最大值一定是$wi$,一共有$a*b$个选法，爱情经验值为$a*b*wi$。 求最小值的和的方法类似。 槽点： 一：这题做数据的时候突然想到的把数据范围设在 unsigned long long 范围内，要爆 long long，这样选手在wa了之后可能心态不好找不到这个槽点，当是锻炼大家的心态和出现wa时的找错能力了，把这放在pretest..很良心的。 二，并查集的时候，用是递归的需要扩栈，一般上$10w$的递归都需要，所以看见有几个FST在栈溢出的，好桑心。 [title]D：Box[/title] 可以把两个人的箱子数目对应到二维坐标中，由于条件限定，第二个人的箱子数目不能多于第一个人，所有的方法数也就是从(0,0)点走到(n,n)点不跨越x=y这一条直线的所有方法数。这是一个经典的问题，他的答案是卡特兰数$\frac{{\rm{1}}}{{n + 1}}C_{2n}^n$. 现在要将这个数字对M=3814697265625取余，n又特别大。那得看看这个数字有什么特殊性。尝试着将M进行质因数分解，发现M=5^18 那么首先计算一下$\frac{{\rm{1}}}{{n + 1}}C_{2n}^n$有多少个5因子。如果>=18结果就是0了。 如果小于18，就要计算$\frac{{\rm{1}}}{{n + 1}}C_{2n}^n$不含5的的部分对M取余。 对于前半部分$\frac{{\rm{1}}}{{n + 1}}$好处理。直接把5除掉，求逆元即可。 对于$C_{2n}^n$先转化一下，$C_{2n}^n = \frac{{(2n)!}}{{n!*n!}}$，现在关键问题是求n!里面不含5的对M取余的结果。 设f(n!)代表n!里面不含5的对M取余的结果 可以用多项来解决这个问题。g(x,n)=(x+1)(x+2)(x+3)(x+4)(x+6)..(x+n)%M，x+d里面的d不是5的倍数。 那么f(n!)=g(0,n)*g(0,n/5)*g(0,n/25)*…*g(0,0)%M 现在的问题关键是如何快速求g(x,n)。 我们可以把g(x,n)分成尽量均匀的两段来计算 Seg1=(x+1)(x+2)(x+3)(x+4)(x+6)*…*(x+5*k-1) Seg2=(x+5*k+1)(x+5*k +2)(x+5*k +3)(x+5*k +4)(x+5*k +6)*…*(x+5*k +5*k-1) 当然末尾还有几项，不过项数不超过10，所以直接暴力乘上来就可以了。 先计算出第一段，然后把5*k+x代入第一段就可以得到第二段，因为我们的x是5的倍数，所以x^18以上的项数对M取余是0的，所以只要保留低18项即可。 这样计算f(n!)的复杂度是log(n)*log(n)*18*18*18,第一个log(n)是除5造成的，第二个log(n)是求多项式乘积产生的，后面两个18是多项式乘法，还有一个18是高精度乘法带来的。

[title]1001 GTY's math problem[/title] 取对数比较就好了$log(a^b)=b*log(a)$,注意会有精度误差 [title]1002 GTY's birthday gift[/title] 显然每次会从可重集中选择最大的两个进行操作,设这两数为$a,b(a>=b)$,操作之后的数一定是操作后集合中最大的,下一次选取的数一定是$a+b$和$a$,这就形成了一个类似于斐波那契数列的东西,矩阵乘法快速幂求前n项和即可,转移矩阵如下 $$ \begin{bmatrix} 1 & 1 &1 \\ 0 & 1 &1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} S_{n-1}\\ F_{n-1}\\ F_{n-2} \end{bmatrix} = \begin{bmatrix} S_n\\ F_n\\ F_{n-1} \end{bmatrix} $$ [title]1003 GTY's gay friends[/title] 一个区间是排列只需要区间和为$\frac{len(len+1)}{2} $($len$为区间长度),且互不相同,对于第一个问题我们用前缀和解决,对于第二个问题,预处理每个数的上次出现位置,记它为pre,互不相同即区间中pre的最大值小于左端点,使用线段树或Sparse Table即可在$O(n)/O(nlogn)$的预处理后 $O(logn)/O(1)$回答每个询问.不过我们还有更简单的hash做法,对于$[1..n]$中的每一个数随机一个64位无符号整型作为它的hash值,一个集合的hash值为元素的异或和,预处理$[1..n]$的排列的hash和原序列的前缀hash异或和,就可以做到线性预处理,$O(1)$回答询问. [title]1004 GTY's game II[/title] 对于序列来说,区间翻转和区间和是Splay的经典操作,而把这个问题扩展到树上,我们只需要对这棵树进行树链剖分,分成$O(logn)$的区间,使用Splay维护即可,单次询问复杂度$O(log^2n)$,请注意使用递归的树链剖分有可能爆栈.我们还可以用Link-Cut Tree来解决,分别维护两棵LCT,一棵维护形态一棵维护值,对不同的操作分别维护即可. P.S. 感谢gaotianyu1350的题面和翻译,感谢验题人hzwer,bakser,感谢Herobs的帮助

[title]1001 Missing number[/title] 直接开一个数组记录某个数字是否出现过，就能找到没有出现的两个数字了。更好的空间为$O(1)$的做法是用$n(n+1) \over 2$减去出现数字可以得到两个数字的和，同理一样的方法也可以得到两个数字的平方和，就能解出这两个数字了。 [title]1002 Fibonacci[/title] Fibonacci序列在$10^9$范围内只有43个数，则它们的乘积不超过$10^9$的数也不会很多，直接搜索即可。 [title]1003 Legal path[/title] 虽然看起来是一道最短路模型的题目，但由于要求了走的边权要递增，就可以设计出动态规划的做法。 先将所有边按照边权排序，要找的就是边列表的一个子序列，使得子序列中所有边起点为1，终点为n，其他边起点终点相连，边权递增且差不小于K。就可以得到一个动态规划的做法，暴力是$O(m^2)$的，而转移的过程每次只针对一个点的所有出边，可以给每个点维护一个随着上一条边的权值上升而总代价减小的栈，就可以把DP的复杂度降低为$O(n+m)$，当然因为要排序，再带一个log也是没问题的。 [title]1004 Flipping coins[/title] 比较常规的题目，建立出两个串构成的自动机以及状态转移，就可以按照题意列出方程，高斯消元即可。这样做是$O((|A|+|B|)^3)$的。 但是题目中需要考虑平局的情况，用double来做高斯消元的精度是完全不够的，一种可行的方案是写一个分数类再高斯消元，当然这里分子分母也需要用高精度，需要比较好的实现。 这道题目是一个游戏的改编：https://en.wikipedia.org/wiki/Penney%27s_game 除此之外还有一个利用KMP的$O(|A|+|B|)$的做法，需要比较繁琐的数学推导，这里就把范围没有设的那么大。

[title]1001 Jump and Jump...[/title] 首先算出每个人的成绩，然后sort一下就好了，考虑$n$的范围只有2或者3，只要用if+swap也是可行的。 [title]1002 Taking Bus[/title] 简单的分类讨论，设$s,x,y$分别表示公交的始发站，起点和终点。大概有这样几种情况：1. $s \le x < y$, 2. $x < s < y$，3. $x < y \le s$， 4. $s \le y < x$, 5. $y < s < x$, 6. $y < x \le s$ 分别写出公式即可。答案应该会超过int，注意要用long long。 [title]1003 Matching on Array[/title] 首先我们考虑$m=1$的情况。给定两个数组$A=\{a_1,a_2,\dots,a_n\}$和$B=\{b_1,b_2,\dots,b_k\}$，问$B$在$A$中出现了几次。令$c_i=\frac{a_{i+1}}{a_i}, 1 \le i < n$，同样令$d_i=\frac{b_{i+1}}{b_i}, 1 \le i < k$，那么上述问题可以转化为$c_i$和$d_i$的模式匹配问题，这个正确性显然，也没有什么好证明的。于是对于$m=1$的情况只有用个kmp即可搞定。 现在考虑$m > 1$的情况，我们考虑用ac自动机来做。考虑到字符集并不是普通的数字，而是一个分数，我们不放搞个分数类，然后用map存转移边。用$m$个模式串（Bob的序列）建好自动机之后，把文本串（Alice的序列）在自动机上跑一遍即可统计出答案。 [title]1004 Funny Game[/title] 题目要求对于任何初始状态都要必胜，我们先把这个条件简化一下，毕竟我们不可能枚举所有的初始状态(总共n!个)。 我们先考虑$\{1,2,\dots,n\}$这个状态的必胜条件——对于任意一对数$(x,y), 1 \le x, y \le n$, Alice都能都把它们变成相同的数。这个条件也显然是充分必要的，随便想想就明白了。然后我们可以发现，如果$\{1,2,\dots,n\}$这个状态能够必胜的话，其他的状态也显然能够必胜。如果这个状态不能够必胜，那根本不需要考虑其他状态了。 于是我们只需要考虑是否对于任意一对数$(x,y), 1 \le x, y \le n$, Alice都能都把它们变成相同的数。这样的状态数只有$O(n^2)$个，我们可以考虑dp来做。先用题目给定的$m$个函数构造出一张有向图，图中每个节点都是数对。仔细想想就会发现我们不能用普通的博弈思路来做，因为这个博弈会形成环，这时候我们考虑从终结状态往回推，得出每个状态的dp值。 令dp[i][j][0/1]表示数对为$(i,j)$，Alice先(1)后(0)手是否必胜。然后我们知道dp[i][i][0/1]都是必胜的，并把这些状态放入队列。我们依次从队列中取出一个状态$(x,y,turn)$，如果$turn=1$，那么这个状态的前驱是Bob的回合，不妨设为$(a,b,0)$，那么如果$(a,b,0)$的后继状态都是Alice必胜的话，那么dp[a][b][0]显然也是Alice必胜的，否则这个状态的值我们目前无法确定。如果$turn=0$,类似的那么这个状态的前驱是Alice的回合，不妨设为$(a,b,1)$，那么如果$(a,b,1)$的后继中有一个状态是Alice必胜的，那么dp[a][b][1]显然也是Alice必胜，考虑到$(x,y,0)$就是Alice必胜的，那么前驱状态$(a,b,1)$必然是Alice必胜。我们每次把必胜状态加入队列，用来更新那些未确定的状态。 最后统计是否每个$(x,y,1)$的状态都是必胜的，如果是那么Alice输出YES，否则输出NO。时间复杂度的话是$O(n^3)$。

[title]1001 Have meal[/title] This is an easy problem. We can find the regular pattern through simulating some small cases. So we can find that the answer is (m-1) % n. Another way to solve this problem is dynamic programming. dp[i][j] indicates the answer of i messes and j words. So the boundary condition are dp[i][1]=0. The transfer formula is dp[i][j]=(dp[i][j-1]+1)%i; . Thus we can preprocess all answers with time complexity of O (100*100). [title]1002 Card[/title] 设Xi代表分数为i的牌在b次操作中是否被选到,Xi=1为选到，Xi=0为未选到 那么期望EX=1*X1+2*X2+3*X3+…+x*Xx Xi在b次中被选到的概率是1-(1-1/x)^b 那么E(Xi)= 1-(1-1/x)^b 那么EX=1*E(X1)+2*E(X2)+3*E(X3)+…+x*E(Xx)=(1+x)*x/2*(1-(1-1/x)^b) [title]1003 Apple[/title] 数据规模比较大，直接暴力行不通。可以对不同的数字进行独立的处理。 先对数据进行排序，然后把每一种数字有多少个统计一下。 因为对于比当前小的数字是不影响当前数字是否被统计的。所以可以只考虑比当前数字大的，记当前要统计的是第i种数字，数字为x，有y个，比当前数字大的有tot个，总共有n个数字。可以先从n个位置中选出y+tot个位置给当前数字和比当前数字大的数。剩下的位置给前面i-1种数字放，前面i-1种数字的排列数可以通过多重集排列轻松计算出来。Dp[i]代表前i种数字的排列数。Dpr[i]代表后i种数字的排列数。接下来就是计算当前数字有几个个被统计进去了。 可以枚举当前数字被统计进去的数目那么数字x被统计进去的总和是 C(n,y+tot)*Dp[i-1]*x*(y+(y-1)*c(tot,1)+(y-2)*c(tot+1,2)+…+1*c(tot+y-2,y-1))*dpr[i+1] C(i,j)为组合数从i个中选j个的方法数。 最后总的复杂度是O(nlogn) [title]1004 Mathematics problem[/title] 这是一个二阶常系数齐次微分方程。 $\left\{\begin{matrix}{f{\left( x \right)}}^{"}=f{\left( x \right)}\\ {f{\left( 0 \right)}=f{\left( 0 \right)}}^{'}=1\end{matrix}\right.$ 先得出特征方程${\lambda ^{\rm{2}}}{\rm{ - }}1{\rm{ = }}0$ 解出$\lambda {\rm{ = }} \pm 1$ 那么$f\left( x \right) = {C_1}{e^x} + {C_2}{e^{ - x}}$ 将初值代入得$f\left( x \right) = {e^x}$ 那么$g\left( x \right) = \frac{x}{{{e^x} - 1}}$ 直接求导很麻烦，可以采用泰勒展开$g\left( x \right) = \sum\limits_{n = 0}^\infty {{a_n}{x^n}} $ 那么 $\mathop {\lim }\limits_{x \to 0} {\kern 1pt} {\kern 1pt} {\kern 1pt} g{\left( x \right)^{\left( n \right)}}$$ = n! * {a_n}$ $g\left( x \right) = \frac{x}{{{e^x} - 1}} = \frac{x}{{\sum\limits_{n = 1}^\infty {\frac{{{x^n}}}{{n!}}} }} = \frac{1}{{\sum\limits_{n = 1}^\infty {\frac{{{x^{n - 1}}}}{{n!}}} }}$ 然后再用FFT求出${\sum\limits_{n = 1}^\infty {\frac{{{x^{n - 1}}}}{{n!}}} }$在MOD x^65536意义下的多项式逆，即可求出前面65536个an了。 多项式的逆可以用倍增法。 设Bt为多项A在模x^t意义下的逆 那么 \[\begin{array}{l} {B_t}*A = 1(mod{\kern 1pt} {\kern 1pt} {x^t})\\ {B_{2t}}*A = 1(mod{\kern 1pt} {\kern 1pt} {x^t}) \end{array}\] 那么有\[{{\rm{B}}_{\rm{t}}} - {B_{2t}} = 0(mod{\kern 1pt} {\kern 1pt} {\kern 1pt} {x^t})\] 两边平方\[{{\rm{B}}^2}_{\rm{t}} - 2{{\rm{B}}_{\rm{t}}}{B_{2t}} + B_{2t}^2 = 0(mod{\kern 1pt} {\kern 1pt} {\kern 1pt} {x^{{\rm{2}}t}})\] 左右两边同乘A \[{\rm{A*}}{{\rm{B}}^2}_{\rm{t}} - 2{{\rm{B}}_{\rm{t}}} + B_{2t}^{} = 0(mod{\kern 1pt} {\kern 1pt} {\kern 1pt} {x^{{\rm{2}}t}})\] 所以\[B_{2t}^{}{\rm{ = - A*}}{{\rm{B}}^2}_{\rm{t}}{\rm{ + }}2{{\rm{B}}_{\rm{t}}}(mod{\kern 1pt} {\kern 1pt} {\kern 1pt} {x^{{\rm{2}}t}})\] 初始条件 这样就可以在nlogn时间内求出多项式的逆了。 ```cpp #include <iostream> #include<stdio.h> #include<algorithm> #include<math.h> #include<string.h> using namespace std; typedef __int64 lld; const int MAX=65536*4; const int MOD=1000000007; void outmat(int a[],int len) { return; for(int i=0;i<len;i++)printf("%d ",a[i]); puts(""); } int P[3],g[3]; int r[3][MAX],tb[MAX]; bool isprime(int n) { int i; for(i=2;i*i<=n;i++)if(n%i==0)return false; return true; } lld mod(lld a,lld b,lld m) { lld ret=1; a%=m; while(b) { if(b&1)ret=ret*a%m; a=a*a%m; b>>=1; } return ret; } bool isroot(int g,int P) { int p1=P-1,i; for(i=1;i*i<=p1;i++) { if(p1%i==0) { if(mod(g,i,P)==1)return false; if(p1/i<p1&&mod(g,p1/i,P)==1)return false; } } return true; } void init(int lim) { int cnt=0,k=1; for(cnt=0;cnt<3;cnt++) { while(true) { P[cnt]=k<<21|1; if(P[cnt]>lim&&isprime(P[cnt])) { for(g[cnt]=1;isroot(g[cnt],P[cnt])==false;g[cnt]++) ; k++; break; } k++; } } } int rev(int n,int bitcnt) { int ret=0; while(bitcnt--) { ret=ret<<1|(n&1); n>>=1; } return ret; } void buildleaf(int a[],int bitcnt) { int full=1<<bitcnt; int i,j; for(i=0;i<full;i++) { j=rev(i,bitcnt); if(j<i)swap(a[i],a[j]); } } void FFT(int a[],int bitcnt,int mode,int P,int g) { buildleaf(a,bitcnt); int s,half; int i,k,full=1<<bitcnt; for(s=2;s<=full;s<<=1) { half=s>>1; lld wn=mod(g,(P-1)/s,P); if(mode==-1)wn=mod(wn,s-1,P); for(i=0;i<full;i+=s) { lld w=1; for(k=0;k<half;k++) { lld u=a[k+i]; lld v=w*a[k+i+half]; if(v>=P)v%=P; if(u+v>=P)a[k+i]=u+v-P; else a[k+i]=u+v; a[k+i+half]=u-v; if(a[k+i+half]<0)a[k+i+half]+=P; w=w*wn%P; } } } if(mode==-1) { lld iv=mod(full,P-2,P); lld tmp; for(i=0;i<full;i++) { tmp=iv*a[i]; if(tmp>=P)tmp%=P; a[i]=tmp; } } } lld CRT(lld r0,lld r1,lld r2,lld p0,lld p1,lld p2) { lld invp0p1=423765473; lld invp0=253231225; lld t0=(r1-r0)*invp0; if(t0>=p1||t0<=-p1)t0%=p1; if(t0<0)t0+=p1; lld y=t0*p0+r0; lld k=(r2-y); if(k>=p2||k<=-p2)k%=p2; k*=invp0p1; if(k>=p2||k<=-p2)k%=p2; if(k<0)k+=p2; lld res=k*p0; if(res>=MOD)res%=MOD; res=(res*p1+y)%MOD; return res; } bool zero(int a[],int n) { for(int i=0;i<n;i++)if(a[i])return false; return true; } bool one(int a[],int n) { if(a[0]!=1)return false; return zero(a+1,n); } int conv(int a[],int b[],int n,int m,int up) { int bitcnt=0; int i,j; if(zero(a,n)) { return n; } else if(zero(b,m)) { a[0]=0; return 1; } else if(one(b,m))return n; else if(one(a,n)) { memcpy(a,b,sizeof(int)*m); return m; } while((1<<bitcnt)<n+m)bitcnt++; int full=1<<bitcnt; for(i=n;i<full;i++)a[i]=0; for(i=m;i<full;i++)b[i]=0; for(i=0;i<3;i++) { memcpy(r[i],a,sizeof(int)*full); memcpy(tb,b,sizeof(int)*full); FFT(r[i],bitcnt,1,P[i],g[i]); FFT(tb,bitcnt,1,P[i],g[i]); lld tmp=0; for(j=0;j<full;j++) { tmp=(lld)tb[j]*r[i][j]; if(tmp>=P[i])tmp%=P[i]; r[i][j]=tmp; } FFT(r[i],bitcnt,-1,P[i],g[i]); } for(i=0;i<full&&i<up;i++) { a[i]=CRT(r[0][i],r[1][i],r[2][i],P[0],P[1],P[2]); } while(i>0&&a[i-1]==0)i--; return i; } lld inv[MAX],invfac[MAX],fac[MAX]; lld B[MAX]; int A[MAX],B0[MAX]; int TA[MAX],TB[MAX]; void minu(int a[],int n) { int i; for(i=0;i<n;i++) { a[i]=-a[i]+MOD; if(a[i]==MOD)a[i]=0; } a[0]+=2; if(a[0]>=MOD)a[0]-=MOD; } int main() { init(1000000000); int i,j; int up=65536; inv[0]=inv[1]=1; invfac[0]=invfac[1]=1; fac[0]=fac[1]=1; for(i=2;i<MAX;i++) { inv[i]=-inv[MOD%i]*(MOD/i)%MOD+MOD; invfac[i]=invfac[i-1]*inv[i]%MOD; fac[i]=fac[i-1]*i%MOD; } for(i=0;i<up;i++) { A[i]=invfac[i+1]; } B0[0]=1; int m=up; for(m=2;m<=up;m<<=1) { memcpy(TA,A,sizeof(int)*m); memcpy(TB,B0,sizeof(int)*(m>>1)); conv(TA,TB,m,m>>1,m); minu(TA,m); conv(B0,TA,m>>1,m,m); } for(i=0;i<up;i++) { lld tmp=fac[i]*B0[i]; if(tmp>=MOD)tmp%=MOD; B[i]=tmp; } lld n; while(scanf("%I64d",&n)!=EOF) { printf("%I64d\n",B[n]); } return 0; } ```