题解 | 小白月赛63

赛后回顾

前五题都挺简单的，第五题是个组合数学题，有种解法值得关注一下
第六题没做出来，赛时是考虑用 $calc(R)-calc(L-1)calc(R)-calc(L-1)$ 的方式去求出区间 $[L,R][L,R]$ 的值，然后考虑对区间大小二分，对于一个特定的区间大小，假设了所有这个大小的区间的值是连续的，然后应该是假了（额，现在仔细想了下，貌似假的很明显，不过赛时第一步就考虑错了也不太可能做出来了）

E

题意

求出n个数的所有排列中包含1和n的所有子区间的个数

解法

假设有 $(n-2)(n-2)$ 个任意排列的数，在这 $(n-2)(n-2)$个数中插入四个空格，分别填入$1,n,L,R1,n,L,R$ ,这样就一一对应了所有满足条件的子区间，此时情况数是 $(n+2)!(n+2)!$ 。注意这四个空格左右两侧必须分别是 $L,RL,R$ ,这种放置在四个数的排列中占比是 $\frac{2!}{4!}\backslash frac\{2!\}\{4!\}$，所以最后的答案是 $(n+2)!\times \frac{2!}{4!}=\frac{(n+2)!}{12}(n+2)!\; \backslash times\; \backslash frac\{2!\}\{4!\}\; =\; \backslash frac\{(n+2)!\}\{12\}$

F

题意

判断是否存在区间 $[L,R][L,R]$ 使得区间内所有数字符串拼接起来的长度等于 $nn$，若存在，求出最小的区间长度，另外有限制

解法

对于区间 $[L,R][L,R]$ ，考虑其涉及的位数区间是 $[l,r][l,r]$ （例如对于区间 $[648,114514][648,114514]$ ，涉及的位数区间就是 $[3,6][3,6]$）
那么位数为 $4,54,5$ 的所有数都是包含的，并且对于特定的位数，每个数的贡献是一样的，总个数也很显然。（例如，位数为 $44$ 的所有数就是 $[1000,9999][1000,9999]$ ，每个数的贡献值都是 $44$ ，总个数是 $9999-1000+1=90009999-1000+1=9000$ ，所以位数为 $xx$ 的所有数的总贡献值就是 $9\times 10^{x-1}\times x9\; \backslash times\; 10^\{x-1\}\; \backslash times\; x$）
考虑如何去凑出 $nn$ ，可以枚举 $l,rl,r$ ，表示 $[L,R][L,R]$ 涉及的位数区间，那么位数区间 $[l+1,r-1][l+1,r-1]$ 中的所有数都是包含的，那么总贡献就是 ${\sum }_{x=l+1}^{r-1}9\times 10^{x-1}\times x\backslash sum\_\{x=l+1\}^\{r-1\}9\; \backslash times\; 10^\{x-1\}\; \backslash times\; x$ ，除此之外还需要考虑位数为 $l,rl,r$ 时的贡献值。
假设位数为 $l,rl,r$ 的个数分别是 $x,yx,y$ 个，那么有等式 $l\times x+r\times y=n^{\mathrm{\prime }}=n-{\sum }_{x=l+1}^{r-1}9\times 10^{x-1}\times xl\; \backslash times\; x\; +\; r\; \backslash times\; y\; =\; n\text{'}\; =\; n\; -\; \backslash sum\_\{x=l+1\}^\{r-1\}9\; \backslash times\; 10^\{x-1\}\; \backslash times\; x$
显然可以通过 $\text{exgcd}\backslash text\{exgcd\}$ 来求解，此外考虑另外一种解法
注意到 $l,rl,r$ 满足这样的限制 $1\le l,r\le 18,l\le r1\; \backslash leq\; l,r\; \backslash leq\; 18,\; l\; \backslash leq\; r$
改写等式为 $l\times x=n^{\mathrm{\prime }}-r\times yl\; \backslash times\; x\; =\; n\text{'}\; -\; r\; \backslash times\; y$
要令 $(n^{\mathrm{\prime }}-r\times y)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}l)(n\text{'}\; -\; r\; \backslash times\; y)\; \backslash equiv\; 0\; \backslash pmod\; l$
考虑枚举 $yy$ ，$(n^{\mathrm{\prime }}-r\times y)\mathrm{m}\mathrm{o}\mathrm{d}l(n\text{'}\; -\; r\; \backslash times\; y)\; \backslash mod\; l$ 的值是存在循环的，$n^{\mathrm{\prime }}-r\times y\equiv n^{\mathrm{\prime }}-r\times (y+l)(\mathrm{m}\mathrm{o}\mathrm{d}l)n\text{'}\; -\; r\; \backslash times\; y\; \backslash equiv\; n\text{'}\; -\; r\; \backslash times\; (y\; +\; l)\; \backslash pmod\; l$
所以循环节的长度为 $ll$ ，而 $l\le 18l\; \backslash leq\; 18$ ，所以直接暴力枚举的复杂度也足够通过此题