闲话
卡了一下午今天 T3
包括但不限于 卡ull 卡非正解ac自动机
《你是不是精神变态啊》 - By 某人
但是最后数据除了卡ull和ac自动机的都没用就是了
今天的歌是Meltyland Nightmare！
Meltyland Nightmare
案外そんなフューチャー
那般的未来难以预料
先天的なフューチャー
天生天化的未来
案外そんなフューチャーだよ
真是意料之外的未来啊
わんつーさんはい、いちにさん
one two three 一二三
そろそろ起きたらどう
慢慢起床怎么样
驚く顔なら知ってるよ
若是惊吓的话 我很明白
いっつもそういう顔をする
你经常会流露出那般神情
Welcome to the メルティランド
Welcome to the melty land
ここはひとりもふたりも無い場所
此无人之境
Welcome to the メルティランド
Welcome to the melty land
美しい夢だけが遺る場所
仅残存美梦之界
貴方はドアを開けたの
你开启此门
僕の世界のドアを選んだの
选择了来到我世界的这扇门
十年前から待っていたわ
十年前我便一直等候
Welcome to the メルティランド
Welcome to the melty land
疑ってしまうような
像是心存怀疑
不可侵のスターリーナイト
这不可侵的星夜
ずっと前の空想が
从前一直幻想
今日の君の白昼夢
今天你做的白日梦
時間すら 止まったら
倘若连时间都暂停
見え始める君のナイトメア
就能看见你的梦魇
正常なグッドモーニング
平日的早安
人生のハッピーエンディング
人生的美满结局
僕達は何ひとつ叶わないのなら
如若我们什么都无法实现
疑ってしまうような
像是心存怀疑
不可侵のスターリーナイト
这不可侵的星夜
一瞬だけ忘れないでよね
只这一瞬请勿忘却
案外そんなフューチャー
那般的未来难以预料
先天的なフューチャー
天生天化的未来
案外そんなフューチャーだよ
真是意料之外的未来啊
君とは今日で五千回目
与你一起今天是
またまた悪夢を観ましたね
第五千次 看到噩梦了呢
お母さんに何か言われたの？
梦到被妈妈训斥了什么吗
クラスの誰かが冷たいの？
被班上的谁冷眼相待了吗
パパが言うには明日隕石が降って
爸爸说 明日天降陨石
世界が瞬く間に終わりを迎える
于刹那之间迎接世界终结
僕はちょっとだけ期待してみた
对此我稍有期待呢
アダムの言いなりはお終い
对神言听计从的世界就要结束了
もう千年前から待っていたわ
千年前便一直等候这天的到来
Welcome to the メルティランド
Welcome to the melty land
疑ってしまうような
像是心存怀疑
とびきりのディナータイム
精致的晚餐时间
溶けあってしまいそうだ
仿佛要融为一体
君と僕のナイトメア
你同我的梦魇
名前すら 夢ん中
甚至名字都在梦中
触れ合うのはガラスハートだけ
只玻璃心可触碰
正常なグッドモーニング
平日的早安
人生のハッピーエンディング
人生的美满结局
僕達は何ひとつ叶わないのなら
如若我们什么都无法实现
疑ってしまうような
像是心存怀疑
とびきりのディナータイム
精致的晚餐时间
一生だけ忘れないでよね
仅这一生请勿忘却
溶けていく
融化着
運命が溶けていく
命运开始融化
ぎゅっとしてしまいそうな
好想紧紧抱住
イノセンスなロンリーガール
天真无邪的孤独少女
泣きたいほど純情だ
纯真的甚至快要哭泣
あとちょっとのナイトメア
即将结束的梦魇
時間すら 止まっても
纵使连时间都暂停
片方だけワガママ言うの
也仅是单方面的任性
朝6時の警鐘が
早上6点的警钟
僕達のタイムオーバー
我们的时间结束了
からからのハートだって息を吸うことを
即使是空洞的心 也想要感受呼吸
ぎゅっとしてしまいそうな
好想紧紧抱住
イノセンスなロンリーガール
天真无邪的孤独少女
目が醒めても忘れないでよね
纵使醒来也请勿忘却我的事
愛したって君は目を覚ます
曾爱过的你醒来
ゼロになってゼロになって
一切归零 消失殆尽吧
愛したって君は僕を忘れる
曾爱过的你 把我忘记
ゼロになって ゼロになって ゼロになって…
一切归零 消失殆尽吧
是在绝望中有着一些希望的歌曲呢。
和《命运》一样，描写的都是梦中的真实。
如果让我翻译的话会是“溶化国度的梦魇”之类的
感觉处理得不是很好
有时候会想看深海。正好手边有风油精。最好是三分之二多的容量，空气和液体比例正好。用手遮一下环境光，让它只能照到表层。使劲摇晃，等待最开始的大气泡上浮消散，你就能看到深海。
深海里有气泡。你能看到的是从无到有慢慢上浮的微小气泡。小小的深海总是使人沉醉。
归根结底我的心态是对未知的好奇。深海这种意象总是体现着人类认知之外的事物，与之相连的总是勇敢的人类的探寻。
想到了洛夫克拉夫特开启的那个世界。因此联想到了一些creepypasta和基金会。
还是要在有着尊重和谦敬的心态下去了解新事物。
数论
给定 \(n\)，求出 \(n!\) 十进制表示下从最末非0位开始的 \(k\) 位。
\(k \in \{1,2,3\}, n \le 10^{200}\)
一眼不可做（
我们设 \(n!\) 中有 \(t\) 个10。那 \(\frac{n!}{10^t}\) 的后 \(k\) 位即为答案，即 \(\frac{n!}{10^t}\ \text{mod}\ {10^k}\) 。
说句废话：\(2 \times 5 = 10\)
因此末尾的0都是由质因子2和5凑出来的。考虑除下去 \(t\) 个2和5使得他们两个在最终结果中不共同存在。
求解此问题需要在 \(\text{mod} \ 10^k\) 意义下进行。直接求是困难的，考虑先求得 \(\text{mod} \ 2^k\) 意义下和 \(\text{mod} \ 5^k\) 意义下的答案。由于一般而言在 \(n!\) 的质因子拆分中2的幂次远大于5的幂次，因此 \(\text{mod} \ 2^k\) 意义下答案一般为0。因此考虑求得 \(\text{mod} \ 5^k\) 意义下的答案后 CRT 合并即可。
我们可以先求出 \(\frac{n!}{5^t}\) 的结果，随后算出 \(t\) 并将结果除下 \(2^t\)。由于 \(2^t\) 与 \(5^k\) 互质，因此可以考虑乘入逆元。计算 \(t\) 是平凡的。现在只要求得 \(\frac{n!}{5^t}\ \text{mod} \ 5^k\) 的结果即可。
考虑 \(n!\) 的每一项除去可能存在的一个质因子5后的结果。
我们首先对5的倍数提出一个5。容易发现提出部分所剩余的内容相乘组成了新的阶乘，但为原问题的规模除5。这部分可以递归求解。非5的倍数的计算考虑 \(\text{mod}\ 5^k\)。这部分 \(\text{mod}\ 5^k\) 的结果是循环的。因此可以先讨论循环节的解再讨论余项的解。形式化地，我们有
前两项是讨论5的倍数对应的新阶乘，后两项分别是循环节的循环次数次幂以及余数部分。
这玩意就是exLucas的公式嘛。直接模拟就可以了。
我们发现结果值域很小，因此没必要写CRT。可以以 \(2^k\) 的gap扫描区间，所得结果在 \(\text{mod}\ 5^k\) 意义下与上方得到的答案相同时输出即可。
时间复杂度 \(O(\log n)\)。记得写高精度，只需要实现一个除和模低精。注意这个方法在没有 \(5\) 的质因子的阶乘时不通用，因此要特判 \(1-5\) 的答案。
code
int T, k, l, ans, tmp, tot, mod[] = {1, 10, 100, 1000}, m5[] = {1, 5, 25, 125};
int fac[130], rem[130];
const int bse = 10000;
char ch[205];
int qp(int a, int b, int mod) { int ret = 1; for (; b; a = 1ll * a * a % mod, b >>= 1) if(b & 1) ret = 1ll * ret * a % mod; return ret; }
struct IA {
int len; int a[105];
void init() {
len = (l - 1) / 4 + 1; memset(a, 0, sizeof a);
rep(i,1,len-1) a[i] = (ch[l - 4 * i] - '0') * 1000 + (ch[l - 4 * i + 1] - '0') * 100 + (ch[l - 4 * i + 2] - '0') * 10 + (ch[l - 4 * i + 3] - '0');
rep(i,1,(l-1) % 4 + 1) a[len] = 10 * a[len] + ch[i-1] - '0';
}
bool operator <= (const int & b) const { return len == 1 and a[1] <= b; }
void operator /= (int rhs) {
for (int i = len; i; --i) a[i-1] += a[i] % rhs * bse, a[i] /= rhs;
while (len and !a[len]) len--;
} int operator % (const int & rhs) const { return a[1] % rhs; }
}n, m;
inline int get_ans(IA nval) {
if (nval <= 125) return fac[nval.a[1]];
int x = nval % 125; nval /= 5;
int ret = get_ans(nval); nval /= 25;
return ret * qp(rem[125], nval % 100, 125) % 125 * rem[x] % 125;
}
inline void put(int val) {
if (k == 3) printf("%03d\n", val % mod[k]);
if (k == 2) printf("%02d\n", val % mod[k]);
if (k == 1) printf("%01d\n", val % mod[k]);
}
fac[0] = rem[0] = 1;
rep(i,1,125) {
tmp = i; while (tmp % 5 == 0) tmp /= 5;
fac[i] = 1ll * fac[i-1] * tmp % 125;
rem[i] = 1ll * rem[i-1] * (i % 5 ? i : 1) % 125;
}
scanf("%d", &T);
while (T--) {
scanf("%s%d", ch, &k);
l = strlen(ch);
n.init(); ans = get_ans(n);
if (n <= 6) { ch[0] -= '0'; if (ch[0] == 1) put(1); if (ch[0] == 2) put(2);if (ch[0] == 3) put(6);if (ch[0] == 4) put(24);if (ch[0] == 5) put(12);if (ch[0] == 6) put(72); continue;}
m = n, tot = 0;
while (m.len) m /= 5, tot = (tot + m % 100) % 100;
ans = ans * qp(63, tot, 125) % 125;
for (int i = 0; i < 1000; i += 8) if (i % 125 == ans) {
put(i); break;
}
}