被虐惨了qwq，写一下题解方便复习吧

---

魔法串

（magic.cpp/c/pas）magic.in magic.out

【问题描述】

小 N 最近在沉迷数学问题。
对于一个数字串 S，如果可以将它划分成两个数字 A、B，满足：
1、 S ̅=(AB) ̅ 。
2、 A、B 均不包含前导 0。
3、 B 是 A 的倍数，且B / A是完全立方数。
那么小 N 就认为该划分是一个“好划分”。 如对于数字串“11297”，（11， 297）就是一个“好划分”。
如果一个数字串 S 至少有两个“好划分”，那么小 N 就认为 S 是一个“魔法串”。 如数字串“1335702375”就是一个“魔法串”，其“好划分”有（1， 335702375）和（133，5702375）。
现在给定正整数 N，小 N 需要你帮她求出一个长度恰好为 N 的“魔法串”S，如果无解请输出“QwQ”（不带引号）。

【输入】

一行一个正整数 N。

【输出】

一行一个长度恰好为 N 的“魔法串”S， 如果无解请输出“QwQ”（不带引号） 。

【输入输出样例】

19

【输出样例】

1124784124392112128

【数据范围】

对于 30%的数据： 1 ≤ N ≤ 10。
对于 50%的数据： 1 ≤ N ≤ 35。
对于 100%的数据： 1 ≤ N ≤ 100。

---

cyw在场上想到打表了，但是打表没有记得去找规律，最后只有可怜的30
打表数据可以发现，若s是膜法串，那么s000也是
所以打一下前几个然后补0就好了，当然了还是打表输出

---

配对

（pair.cpp/c/pas）pair.in pair.out

【问题描述】

有1~n一共n个数，n为偶数。小Q要把这n个数随机地两两配对。令每一对的权值为它们两个数的和。小Q想要知道这n对里最大的权值的期望是多少。请输出答案对10^9+7取模的值。

【输入】

一行一个正整数 N。

【输出】

一行一个整数，表示答案对10^9+7取模的值。

【输入样例】

4

【输出样例】

6

【数据范围】

对于 20%的数据： 1 ≤ N ≤ 10。
对于 40%的数据： 1 ≤ N ≤ 2000。
对于 100%的数据： 1 ≤ N ≤ 500000。

---

cyw在场上还是只会打表qwq，分数依旧很可怜

标算

考虑答案是否能>=v" role="presentation" style="position: relative;">>=v$>=v$
转化为答案是否能<=v" role="presentation" style="position: relative;"><=v$<=v$
∑v(pv−pv−1)v" role="presentation">∑v(pv−pv−1)v$$\sum _v(p_v-p_{v-1})v$$
把1..n分为两部分，一部分是>v2" role="presentation" style="position: relative;">>v2$>\frac{v}{2}$的，另一部分是<=v2" role="presentation" style="position: relative;"><=v2$<=\frac{v}{2}$的
显然只能从>v2" role="presentation" style="position: relative;">>v2$>\frac{v}{2}$和<v2" role="presentation" style="position: relative;"><v2$<\frac{v}{2}$里进行匹配
我们每次从大到小枚举>v2" role="presentation" style="position: relative;">>v2$>\frac{v}{2}$的部分，每次有v−n" role="presentation" style="position: relative;">v−n$v-n$种选择，
故方案数为
(v−n)n−v2" role="presentation">(v−n)n−v2$$(v-n{)}^{n-\frac{v}{2}}$$ 剩下的部分是一个完全图，令f(x)" role="presentation" style="position: relative;">f(x)$f(x)$为x" role="presentation" style="position: relative;">x$x$个点的方案数，则f(x)=1×3×5×...×(x/2)" role="presentation" style="position: relative;">f(x)=1×3×5×...×(x/2)$f(x)=1\times 3\times 5\times ...\times (x/2)$
预处理阶乘后可以O（NlogN）" role="presentation" style="position: relative;">O（NlogN）$O（NlogN）$计算

---

幸运数

（lucky.cpp/c/pas）lucky.in lucky.out

【问题描述】

对于任意两个非零整数x，y，若整数d能同时被x和y整除，则称d为x与y的公约数。定义x与y的最大公约数gcd(x, y)为x与y的最大的公约数。
如gcd(6, 9) = 3，gcd(12, 16) = 4，gcd(25, 32) = 1，等等。 这里，我们定义什么是幸运数： 对于一个正整数d，我们使用di表示d在十进制表示下，按从低位到高位顺序的第i位数字。
设F(d)表示d的奇数位的数字之和，即F(d) = d1 + d3 + d5 + ……；
设G(d)表示d的偶数位的数字之和，即G(d) = d2 + d4 + d6 + ……；
若F(d)与G(d)均大于0，且F(d)与G(d)的最大公约数不超过K，则称d为幸运数。其中K是一个已知的常数。 举个例子来说，若d = 641，则d1 = 1，d2 = 4，d3 = 6，F(641) = 1 + 6 = 7，G(641) = 4。此时F(d)与G(d)的最大公约数即gcd(7, 4)等于1。则当K不小于1时641是幸运数。 小M请你回答下面的问题：
对于给定的K，在不小于L并且不超过R的所有整数中，有多少个数是幸运数？
注意，输入文件包含多组测试数据。

【输入文件】

第一行包含一个整数T，表示有T组测试数据。
接下来T行，每行包含三个整数K、L、R，表示一次询问。

【输出文件】

输出T行，每行一个整数，依次表示每组测试数据的答案。

【输入样例】

5
1 1 10
2 28 34
100 987654321 987654321
1 1 50000
1 50001 100000

【输出样例】

0
5
1
30298
30309

【样例解释】

K = 1时，1到10之间不存在幸运数。 K = 2时，28到34之间的幸运数有28、29、31、32、34，共5个。
K = 100时，987654321是幸运数。
K = 1时，1到50000之间的幸运数有30298个，50001到100000之间的幸运数有30309个。

【数据规模和约定】

对于10%的数据：1≤L≤R≤103。" role="presentation" style="position: relative;">1≤L≤R≤103。$1\le L\le R\le {10}^3。$
另有10%的数据：1≤L≤R≤107，1≤K,T≤10。" role="presentation" style="position: relative;">1≤L≤R≤107，1≤K,T≤10。$1\le L\le R\le {10}^7，1\le K,T\le 10。$
另有10%的数据：1≤L≤R≤109，K=1，1≤T≤10。" role="presentation" style="position: relative;">1≤L≤R≤109，K=1，1≤T≤10。$1\le L\le R\le {10}^9，K=1，1\le T\le 10。$
对于60%的数据：1≤L≤R≤1012，1≤K,T≤102。" role="presentation" style="position: relative;">1≤L≤R≤1012，1≤K,T≤102。$1\le L\le R\le {10}^{12}，1\le K,T\le {10}^2。$
对于100%的数据：1≤L≤R≤1018，1≤K≤102，1≤T≤1000。" role="presentation" style="position: relative;">1≤L≤R≤1018，1≤K≤102，1≤T≤1000。$1\le L\le R\le {10}^{18}，1\le K\le {10}^2，1\le T\le 1000。$

---

只写了10分部分分qaq
分块打表可以拿30
标算是数位dp，垃圾cyw又不会，不想写了