_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

Description

有一些{1n}\{1\dots n\}的子集Ai,j,1jikA_{i,j}, 1\leqslant j\leqslant i\leqslant kk(k+1)2\frac{k(k+1)}2个,满足Ai,jAi+1,j,Ai,jAi,j+1A_{i,j}\subset A_{i+1,j}, A_{i,j}\subset A_{i,j+1}。求这些集合有多少种方案。如果AABB两种方案中存在i,ji,j使得Ai,jBi,jA_{i,j}\neq B_{i,j},则它们是不同的。n,k109n, k\leqslant 10^9

阅读全文 »

Description

nn个点的树,qq个询问,每个询问给出l,r,xl,r,x,求i=lrdeplca(i,x)\sum_{i=l}^r dep_{lca(i, x)}。根的深度是11n,q50000n, q\leqslant 50000
阅读全文 »

Description

定义一个图的变换:对于一个有向图G=(V,E)G=(V, E),建立一个新的有向图:

V={veeE}V'=\{v_e|e \in E\}E={(vb,ve)b=(u,v),e=(v,w)}E'=\{(v_b, v_e)|b=(u,v), e=(v,w)\}G=(V,E)G'=(V', E')

也就是说每个边变成一个点,如果边b的终点和边e的起点相同则b到e连一条边。

现在给定GG',问是否存在GGGG'的点数不超过300300

阅读全文 »

Description

平面上有nn个位置1n1\dots n,第ii个位置有一个高为HiH_i的楼房;所有HH初始值为00。每次修改一个HiH_i,求修改后从(0,0)(0,0)点可以看到多少楼房。n,m105n,m\leqslant10^5

阅读全文 »

Description

给定n,mn,m,求

i=1nj=1m[ij](nmodi)(mmodj)\sum_{i=1}^n\sum_{j=1}^m[i\neq j](n\,mod\,i)(m\,mod\,j) n,q109n, q\leqslant10^9
阅读全文 »

Description

kk堆石子,两个人游戏:
  • 首先,A拿走若干堆石子(不能全部拿走)

  • 之后,B拿走若干堆石子(不能全部拿走)

  • 然后从A开始NimNim游戏。

问A能不能取胜。如果能,A第一步至少要拿走多少石子?

阅读全文 »

Description

一个nn个点的图,从11开始每次随机选择相邻的边走过去直到走到nn为止。

现在你要对mm条边重新从11mm标号,使得路径上期望边权和最小。问最小值。

阅读全文 »

Description

定义

fk(n)=1ingcd(i,n)=1ikf_k(n)=\sum_{\substack{1\leqslant i\leqslant n\\gcd(i,n)=1}}i^k

给出n=i=1wpiain=\prod_{i=1}^w p_i^{a_i},求fk(n)f_k(n)1w1000,1qi,ai1091\leqslant w\leqslant 1000, 1\leqslant q_i,a_i\leqslant 10^9。保证pip_i都为质数且互不相同。

阅读全文 »

Description

一个自动刷题机,每次有两种操作:写下xx行代码或删除xx行代码(不足则全部删除)。存在一个nn,每当代码量大于等于nn时将提交一次并把代码全部删除。已知每次的操作类型和xx,已知一共提交了kk次,问nn的最大值和最小值。

阅读全文 »