「解題報告」2023-10-29 模擬賽
魔法串
（magic.cpp/c/pas）magic.in magic.out
【問題描述】
小 \(N\) 最近在沉迷數學問題。
對于一個數字串 \(S\)，如果可以將它劃分成兩個數字 \(A\)、\(B\)，滿足：
1、 。
2、 \(A\)、\(B\) 均不包含前導 \(0\)。
3、 \(B\) 是 \(A\) 的倍數，且\(\dfrac{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 \le N \le 10\)。
對于 \(50\%\) 的數據： \(1 \le N \le 35\)。
對于 \(100\%\) 的數據： \(1 \le N \le 100\)。
當 \(N \le 4\) 時無解。
如果數字串 \(S\) 是一個魔法串，那么向 \(S\) 后面添加 “\(000\)” 后得到的新串也是一個魔法串。那所以只需要求出 \(N = 5、6、7\) 時的可行解，就可以推廣到所有情況。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define orz puts("sym, cjx, gjh AK IOI!!!");
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 40;
int n, tmpn;
int num[N];
bool vis[10000005];
void work() {
int cnt = 0;
rep (i, 2, tmpn, 1) {
bool fg = 0;
ll res1 = 0, res2 = 0;
rep (j, 1, i - 1, 1) {
res1 = res1 * 10 + num[j];
if (!res1) {
fg = 1;
break ;
}
}
if (fg) continue ;
rep (j, i, tmpn, 1) {
res2 = res2 * 10 + num[j];
if (!res2) {
fg = 1;
break ;
}
}
if (fg) continue ;
if (res2 % res1 == 0) {
ll tmp = res2 / res1;
if (!vis[tmp]) continue ;
++ cnt;
}
}
if (cnt < 2) return ;
rep (j, 1, tmpn, 1) {
printf("%d", num[j]);
}
rep (j, tmpn + 1, n, 1) {
printf("0");
}
putchar('\n');
exit(0);
}
void dfs(int u) {
if (u > tmpn) {
work();
return ;
}
rep (i, 0, 9, 1) {
if (i == 0 && u == 1) {
continue ;
}
num[u] = i;
dfs(u + 1);
}
}
int main() {
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
for (ll i = 1; i <= 1000; ++ i) {
if (i * i * i > 10000000) break ;
vis[i * i * i] = 1;
}
n = read<int>();
int tmp = n - 4;
tmp %= 3;
switch(tmp) {
case 0:
tmpn = 7;
break ;
case 1:
tmpn = 5;
break ;
case 2:
tmpn = 6;
break ;
}
dfs(1);
puts("QwQ");
fclose(stdin);
fclose(stdout);
return 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 \le N \le 10\)。
對于 \(40\%\) 的數據： \(1 \le N \le 2000\)。
對于 \(100%\) 的數據： \(1 \le N \le 500000\)。
考慮枚舉答案是否\(\ge v\)
轉化成答案是否\(\le v\)
把\(1-n\)分成兩部分，一部分是\(>\frac{v}{2}\)的，一部分是\(\le \frac{v}{2}\)的。
顯然\(>\frac{v}{2}\)的只能和\(\le\frac{v}{2}\)的匹配。
我們從大到小枚舉\(>\frac{v}{2}\)的部分，每次都有\(v-n\)種選擇，故方案數為
剩下的部分是一個完全圖，令\(f(x)\)為\(x\)個點的方案數,\(f(x)\)為\(1 \times 3 \times 5 \times \cdots \times (x/2)\)
預處理階乘后可以\(O(nlogn)\)進行計算。
// The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
template<typename T>
void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
template<typename T>
void print(T x, char c) {
write(x);
putchar(c);
}
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
ll n;
ll inv[N], pri[N];
ll qpow(ll x, ll y) {
ll ret = 1;
while (y) {
if (y & 1) {
ret = ret * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return ret;
}
int main() {
freopen("pair.in", "r", stdin);
freopen("pair.out", "w", stdout);
n = read<int>();
inv[0] = pri[0] = 1;
rep (i, 1, n / 2, 1) {
pri[i] = pri[i - 1] * (2 * i - 1) % mod;
}
inv[n / 2] = qpow(pri[n / 2], mod - 2) % mod;
per (i, n / 2 - 1, 1, 1) {
inv[i] = inv[i + 1] * (2 * i - 1) % mod;
}
ll ans = 0, las = 0;
rep (v, n + 1, 2 * n - 1, 1) {
int k = n - v / 2;
ll z = qpow(v - n, k) % mod * pri[v / 2 - n / 2] % mod;
ans = (ans + 1ll * v * (((z - las) % mod + mod) % mod) % mod) % mod;
las = z;
}
printf("%lld\n", (ans * inv[n / 2]) % mod);
return 0;
}
幸運數
（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\)，我們使用 \(d_i\) 表示 \(d\) 在十進制表示下，按從低位到高位順序的第 \(i\) 位數字。
設 \(F(d)\) 表示 \(d\) 的奇數位的數字之和，即 \(F(d) = d_1 + d_3 + d_5 + \cdots\)；
設 \(G(d)\) 表示 \(d\) 的偶數位的數字之和，即 \(G(d) = d_2 + d_4 + d_6 + \cdots\)；
若 \(F(d)\) 與 \(G(d)\) 均大于 \(0\)，且 \(F(d)\) 與 \(G(d)\) 的最大公約數不超過 \(K\)，則稱 \(d\) 為幸運數。其中 \(K\) 是一個已知的常數。
舉個例子來說，若 \(d = 641\)，則 \(d_1 = 1, d_2 = 4, d_3 = 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 \le L \le R \le 10^3\)。
另有 \(10\%\) 的數據：\(1 \le L \le R \le 10^7，1 \le K, T \le 10\)。
另有 \(10\%\) 的數據：\(1 \le L \le R \le 10^9，K = 1，1 \le T \le 10\)。
對于 \(60\%\) 的數據：\(1 \le L \le R \le 10^{12}，1 \le K, T \le 10^2\)。
對于 \(100\%\) 的數據：\(1 \le L \le R \le 10^{18}， 1 \le K \le 10^2，1 \le T \le 1000\)。
60 pts：
設 \(f(i, sum1, sum2)\) 為在第 \(i\) 位，奇數位上的數的和為 \(sum1\)，偶數位上的數的和為 \(sum2\)，進行數位 DP。
// The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
template<typename T>
void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
template<typename T>
void print(T x, char c) {
write(x);
putchar(c);
}
int T;
ll k, l, r;
int a[100];
ll f[25][180][180];
ll dfs(int dig, int lim, ll sum1, ll sum2) {
if (dig == 0) {
if (sum1 && sum2 && __gcd(sum1, sum2) <= k) {
return 1;
}
return 0;
}
if ((!lim) && (~f[dig][sum1][sum2])) {
return f[dig][sum1][sum2];
}
int num = lim ? a[dig] : 9;
ll ans = 0;
rep (i, 0, num, 1) {
ll tmp1 = sum1, tmp2 = sum2;
if (dig & 1) {
tmp1 += i;
} else {
tmp2 += i;
}
ans += dfs(dig - 1, lim && i == a[dig], tmp1, tmp2);
}
if (!lim) {
f[dig][sum1][sum2] = ans;
}
return ans;
}
ll solve(ll n) {
int cnt = 0;
while (n) {
a[++ cnt] = n % 10;
n /= 10;
}
return dfs(cnt, 1, 0, 0);
}
void work() {
memset(f, -1, sizeof f);
k = read<ll>(), l = read<ll>(), r = read<ll>();
cout << solve(r) - solve(l - 1) << '\n';
}
int main() {
freopen("lucky.in", "r", stdin);
freopen("lucky.out", "w", stdout);
T = read<int>();
while (T --) {
work();
}
return 0;
}
浙公網安備 33010602011771號