果然 (color{black}Scolor{red}{iyuan}) 大佬做的题不是我等凡人所能理解的.
Description
题目链接: UOJ #73
本题是一道提交答案题，一共有 (10) 个测试点。
对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。
遗憾的是这些程序效率都极其低下，无法在比赛的 (5) 小时内得到输出。
你需要帮助B君得到这些程序的输出。
Program1
Description
求两个数相乘并取模.
Solution
Python大法吼啊
Code
不需要了吧
Answer
11239440904485
7551029211890
20677492996370
592966462292420
69231182718627
479525534330380
544015996901435
214227311823605
73749675429767
239498441843796
Program2
Solution
观察可以发现:
[aleftarrow 1a+2b+1c
]
[bleftarrow 1a+1b+0c
]
[cleftarrow 1a+0b+0c
]
珂以构造转移矩阵:
[left[
egin{matrix}
1 & 2 & 1 \
1 & 1 & 0 \
1 & 0 & 0
end{matrix}
ight]
]
直接跑矩阵快速幂就好啦.
Code
#include <bits/stdc++.h>
typedef long long ll;
ll a[5][5], ans[5][5];
inline void pp(ll b, ll p) {
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
ans[i][j] = a[i][j];
--b;
for (; b; b >>= 1) {
if (b & 1) {
ll c[5][5];
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
c[i][j] = 0ll;
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
for (int k = 1; k <= 3; ++k)
c[i][j] = (c[i][j] + ans[i][k] * a[k][j] % p) % p;
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
ans[i][j] = c[i][j];
}
ll c[5][5];
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
c[i][j] = 0ll;
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
for (int k = 1; k <= 3; ++k)
c[i][j] = (c[i][j] + a[i][k] * a[k][j] % p) % p;
for (int i = 1; i <= 3; ++i)
for (int j = 1; j <= 3; ++j)
a[i][j] = c[i][j];
}
}
int main() {
freopen("program2.in", "r", stdin);
freopen("program2.out", "w", stdout);
for (int i = 0; i < 10; ++i) {
ll n, p; scanf("%lld%lld", &n, &p);
a[1][1] = a[1][3] = a[2][1] = a[2][2] = a[3][1] = 1, a[1][2] = 2;
a[2][3] = a[3][2] = a[3][3] = 0;
pp(n, p);
ll d = (ans[1][1] + ans[3][1] - ans[2][1] * 2 + p + p) % p;
printf("%lld
", d);
}
return 0;
}
Answer
0
1
96
64
2503
2523
4452160
557586868
959316082
1107500137
Program3
Solution
就是一个零次方到四次方的求和.
背公式+Python就好啦
[sum_{i=1}^{n}i=frac{n(n+1)}{2}
]
[sum_{i=1}^{n}i^2=frac{n(n+1)(2n+1)}{6}
]
[sum_{i=1}^{n}i^3=frac{n^2(n+1)^2}{4}
]
[sum_{i=1}^{n}i^4=frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}
]
Code
Python还要什么代码
Answer
1000000000000001
1000000000000001
2538972135152631808
2538972135152631808
2806098670314569728
2806098670314569728
6570342264898322432
6570342264898322432
10067259324320137216
10067259324320137216
Program4
Solution
count1 : 计算有多少无序点对均为 (1) ,只要计算 (1) 的个数即可.
count2 : 计算每个 (1) 离它曼哈顿距离最近的 (0) 的距离之和,从 (0) 开始宽搜即可.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, 1, 0, -1 };
const int MAXN = 5010, MAXM = 5010;
int n, m, type, seed;
int dis[MAXN][MAXM], vis[MAXN][MAXM];
bool BOOM[MAXN][MAXM];
struct Node {
int x, y;
};
int next_rand(){
static const int P = 1000000007, Q = 83978833, R = 8523467;
return seed = ((ll)Q * seed % P * seed + R) % P;
}
inline void deal1(int n, int m) {
ll cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cnt += BOOM[i][j];
printf("%lld
", cnt * (cnt - 1));
return;
}
inline void deal2(int n, int m) {
queue <Node> Q;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
vis[i][j] = 0;
if (BOOM[i][j] == false) {
vis[i][j] = 1, dis[i][j] = 0;
Q.push(Node { i, j } );
}
}
while (!Q.empty()) {
Node now = Q.front(); Q.pop();
int x = now.x, y = now.y;
for (int k = 0; k < 4; ++k) {
int x1 = x + DX[k], y1 = y + DY[k];
if (x1 && y1 && x1 <= n && y1 <= m && !vis[x1][y1]) {
vis[x1][y1] = 1, dis[x1][y1] = dis[x][y] + 1;
Q.push(Node { x1, y1 } );
}
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += (ll) dis[i][j];
printf("%lld
", ans);
return;
}
int main() {
freopen("program4.in", "r", stdin);
freopen("program4.out", "w", stdout);
scanf("%d", &seed);
for (int t = 0; t < 10; ++t) {
int n, m, type; scanf("%d%d%d", &n, &m, &type);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
BOOM[i][j] = bool(next_rand() % 8 > 0);
if (!type) deal1(n, m);
else deal2(n, m);
}
return 0;
}
Answer
65300
768644095452
1614752
12299725860312
6474661
480452490358302
40508992
480453060258360
40509116
40508835
Program5
Description
计算有多少个全为 (1) 的矩阵.
Solution
单调栈裸题.
但是......
Code
弄丢了......
Answer
36798
780109
4970330
19778353
79444881
183972917
324090457
401682783
493647857
493666110
Program6
Description
计算 (f^{(n)}(t)), 其中 (f(t)=at^2+b).
Solution
显然,这个函数到后来一定会进入一个循环.
容易想到用 (Floyd) 判圈算法.
让快指针每次走 (2) 步,慢指针每次走 (1) 步,当两个指针第一次相遇时,让慢指针回到起点,两个指针再一起走,相遇时必在环的起点.(证明显然,留给读者做练习)
不过窝用的是 (Brent) 判圈 ( exttt{QAQ}).
3分钟就能跑出结果
Code
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull n, a, b, c, s, t, Step_s, Step_t, Steps;
int main() {
freopen("program6.in", "r", stdin);
freopen("program6.out", "w", stdout);
for (int T = 10; T--;) {
scanf("%llu%llu%llu%llu", &n, &a, &b, &c);
s = t = 0;
Step_s = 0, Step_t = 2;
while (2333) {
t = (a * t * t + b) % c;
++Step_s;
if (s == t) break;
if (Step_s == Step_t) {
Step_s = 0, Step_t <<= 1;
s = t;
}
}
s = t = 0;
Steps = 0;
while (Steps < Step_s) {
++Steps;
t = (a * t * t + b) % c;
}
Steps = 1;
while (s != t) {
s = (a * s * s + b) % c;
t = (a * t * t + b) % c;
++Steps;
}
Step_t = (n - Steps) % Step_s + 1;
Steps = 1;
while (Steps <= Step_t) s = (a * s * s + b) % c, ++Steps;
printf("%llu
", s);
}
return 0;
}
Program7
Solution
数独.
用 ( exttt{DLX}) 跑得飞快, 不过其实倒着爆搜也只要几秒.
Code
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
using namespace std;
bool a[20][20], b[20][20], c[20][20], vis[20][20];
int Q[20][20];
bool flag;
inline int calc(int x, int y) {
return x / 4 * 4 + y / 4;
}
void dfs(int x, int y) {
if (x == -1) flag = true;
else {
if (vis[x][y]) {
if (y == 0) dfs(x - 1, 15);
else dfs(x, y - 1);
} else {
rep(i, 0, 15)
if (!flag && !a[x][i] && !b[y][i] && !c[calc(x, y)][i]) {
a[x][i] = b[y][i] = c[calc(x, y)][i] = true;
Q[x][y] = i;
if (y == 0) dfs(x - 1, 15);
else dfs(x, y - 1);
a[x][i] = b[y][i] = c[calc(x, y)][i] = false;
}
}
}
return;
}
int main() {
freopen("program7.in", "r", stdin);
freopen("program7.out", "w", stdout);
rep(t, 0, 3) {
rep(i, 0, 15) rep(j, 0, 15) a[i][j] = b[i][j] = c[i][j] = vis[i][j] = false;
rep(i, 0, 15) rep(j, 0, 15) Q[i][j] = 0;
rep(i, 0, 15) rep(j, 0, 15) {
char ch = getchar();
for (; !((ch >= 'A' && ch <= 'P') || ch == '?'); ch = getchar());
if (ch == '?') continue;
vis[i][j] = true;
int v = ch - 'A';
a[i][v] = b[j][v] = c[calc(i, j)][v] = true;
Q[i][j] = v;
}
flag = false;
dfs(15, 15);
rep(k, 0, t) {
if (!flag) puts("NO SOLUTION.");
else {
rep(i, 0, 15) rep(j, 0, 15) putchar(Q[i][j] + 'A');
puts("");
}
}
}
return 0;
}
Program8
Description
求满足一些不等式的七元组有几个.
Solution
显然是关于 (n) 的七次多项式.
先用程序把 (1-8) 的结果跑出来.
然后根据一些组合数学知识和因式定理或拉格朗日插值糊算出多项式.
(Problem 1)
[C_{n}^{7}
]
(Problem 2)
[frac{1}{60}n^2(n-1)^2(2n-1)(2n^2-2n+1)
]
(Problem 3)
[frac{1}{360}n^2(n-1)(n-2)(2n-1)(7n-3)
]
(Problem 4)
[frac{1}{48}n^3(n-1)^2(n-2)(3n-1)
]
(Problem 5)
[frac{1}{24}n^4 (n-1) (n-2) (n-3)
]
(Problem 6)
[frac{1}{60}n^3 (n-1) (n-2) (3n^2-6n+1)
]
(Problem 7)
[frac{1}{360}n^3 (n-1) (n-2) (n-3) (5n^2-9n+1)
]
(Problem 8)
[frac{1}{144}n^2 (n-1)^2 (2n-1) (5n^2-5n+2)
]
(Problem 9)
[frac{1}{36}n^3 (n-1)^2 (n-2) (2n-1)
]
(Problem 10)
[frac{1}{240}n^2 (n-1)^2 (n-2) (n-3) (2n-3)
]
Oeis大法吼啊!
然后就交给Python
Code
无
Answer
1018333390
993704934
1053807588
1144151985
712062141
530076748
520686243
337499021
820275783
80253986
Program9
Description
给你 (10) 个 ( exttt{MD5}) 值并解密.
Solution
其实就是猜谜......
没什么好说的.
前两个是常识.(1984 和 123456)
第三个大眼观察发现是 chenlijie.
第四个,因为特殊字符只有没几个,枚举并验证可得$_$
五到八个都是一个单词,发现第二个程序后面有一个单词表,逐一试验可得分别为we,hold,these,truths.
第九个是两个单词,历史较好的同学应该可以想到了,没想到也没关系,暴力还是可以过的,得到to be.
最后一个拿头过,显然为 selfevident.
(最后六个是《独立宣言》中的一句话)
Code
无
Answer
1984
123456
chenlijie
$_$
we
hold
these
truths
to be
selfevident
Program10
Solution
我们发现程序的瓶颈在于 A 到 Z 函数,而其他单词调用的次数不多,而 A 到 Z 函数的本质就是若干次 _ 函数,处理就可以啦.
Code
(这么长的代码就不放辣,只放 A 到 Z)
void A(){__+=___*26ull;}
void B(){__+=___*651ull;}
void C(){__+=___*15651ull;}
void D(){__+=___*360651ull;}
void E(){__+=___*7950651ull;}
void F(){__+=___*167340651ull;}
void G(){__+=___*3355140651ull;}
void H(){__+=___*63923340651ull;}
void I(){__+=___*1154150940651ull;}
void J(){__+=___*19688020140651ull;}
void K(){__+=___*316229927340651ull;}
void L(){__+=___*4764358535340651ull;}
void M(){__+=___*67038159047340651ull;}
void N(){__+=___*876597565703340651ull;}
void O(){__+=___*10591310445575340651ull;}
void P(){__+=___*6772687681910030955ull;}
void Q(){__+=___*5479948192676037227ull;}
void R(){__+=___*12292036863279645291ull;}
void S(){__+=___*11448514006979854955ull;}
void T(){__+=___*5543854012881322603ull;}
void U(){__+=___*7009382195709231723ull;}
void V(){__+=___*14337023109848777323ull;}
void W(){__+=___*6754098618987856491ull;}
void X(){__+=___*2452069220114645611ull;}
void Y(){__+=___*12294754496077775467ull;}
void Z(){__+=___*3690695698331353707ull;}
Answer
6754098618987872142
12891177331947568152
12891177331947568152
14433265847896447980
14433265847896447980
15363876303000165384
15363876303000165384
15363876303000165384
15363876303000165384
15363876303000165384
(color{black}{S}color{red}{iyuan}) 大佬太强辣,把我吊起来打!
其实很多都是 (color{black}Scolor{red}{iyuan}) 大佬教我的 ( exttt{QwQ}).
在此 (\%\%\%color{black}Scolor{red}{iyuan}).