AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖

0 说在之前

我吐了,这题我写了两天……

考虑到我自己写的博客还没有 AC 自动机的,我会简单写一下

1 AC 自动机

1.0 什么是 AC 自动机

有一个说烂但是很形象的说法 Trie + KMP

AC 自动机用于多模式串匹配

就是你拿一个字符串,和一堆字符串

然后 AC 自动机可以让你快速的知道这一堆字符串中,那些是你这一个字符串的子串

Continue reading “AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖”

重学后缀数组 — LOJ 2122 「NOI2015」品酒大会

0 说在之前

jt 学长说的没错,SA 果然是写一次忘一次……

于是这次重新学了一次,发现之前的 Blog 问题比较多,于是重写一次算了

实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页,不过是写给自己的罢了

Continue reading “重学后缀数组 — LOJ 2122 「NOI2015」品酒大会”

笔记 — 如何快速的配置一台新手机到我想要的样子

0 事出有因

因为老手机被拿来腾讯会议了,加之确实也算得上时代的眼泪了(

所以换了一台 Redmi K30 5G picasso

那么,开始迁移吧

1 选择 ROM

拿老账号一下就解锁了,没有等待时间,赞美小米

到 XDA 论坛上看一眼没有什么坏处

目测这个手机没有什么好包,Lineageos 都只有一个 alpha 的非官方版,还是 3 个月前的产物了… 详情看这个帖子

不过有一个 eu 版的 miui 包,走起 在这个帖子里

事实上 CN 版的 MIUI 也不错,不过人在 CN 身不由己。我相信小米有保护用户信息的决心(至少 MIUI 12 中可见一二),但是不清楚小米能不能做到。

而且 EU 版有 Google 全家桶,so why not?

Continue reading “笔记 — 如何快速的配置一台新手机到我想要的样子”

随记 – Firefox 扩展

0 事出有因

之前手滑执行了一次命令,导致 Firefox 的配置文件没了

然后操作失误,把云端备份的插件列表搞没了

万幸的是目前整理到的损失似乎只有这些,那就顺便整理一下自己的插件吧

1 插件

1.1 美化

事实上,Firefox 默认主题挺好看的

配合 Arc Theme 可以得到更好的显示效果,何乐而不为

Firefox 默认的标签页有点单调。啥都不显示没意思,显示的东西又没啥用……

所以使用 Tabliss 是一个不错的选择

1.2 标签页

当你标签页血多的时候,Firefox 会在标签栏提供一个滚动条

虽然很人性化,但是明显不够用啊

使用 OneTab 可以归档标签页。毕竟一般开那么多个标签页,真正在用的也没几个

使用 Tree Style Tab 可以给以树形结构管理标签页,改变线性的标签页整理方式

1.3 屏蔽一些恼人的东西

uBlock Origin

广告屏蔽,比 AdblockPlus 快多了

uBlacklist

配合 cobaltdisco/Google-Chinese-Results-Blocklist 使用,可以在 Google 屏蔽掉大部分 SEO 站

什么时候中文互联网的 SEO 站能少一点

1.4 功能扩展

Violentmonkey

暴力猴,在 https://greasyfork.org/zh-CN 或者是 Github 上搞到脚本后就往这东西里面放

我使用的脚本有这些

To Google Translate

用这个可以通过快捷键直接把选中内容送到 Google Translate 里

Aria2 Download Manager Integration

捕获下载链接,直接传给 Aria2

后台挂两个 Aria2,配合这个使用体验不错

不过,这个插件自带的 webui 不太可用,会自动覆盖设置

不过你都后台挂两个 Aria2 了,顺手搭个 httpd 挂个 Aria2 webui 应该也很简单

1.5 安全性

HTTPS Everywhere

重写一些 http 请求为 https,防止某些网站/运营商耍流氓

Firefox Multi-Account Containers

对于国内的毒瘤,除了独立沙箱,应该没有什么防的住 ta 作恶的

这个插件提供了容器功能,你可以把你觉得不太行的网页每次用指定容器打开

终于不用隐私模式用 Baidu 了

2 一点设置

把性能里的线程调小点

Firefox 的个性化可以避免一堆插件挤在你得地址栏上,毕竟你经常会调整设置的插件也就那么几个

3 为什么使用 Firefox

这个问题实际上是没有答案的,浏览器这种东西比较偏个人。你喜欢那个,那个就是对的

不过这里还是给几个理由

Firefox 曾经是比 Chrome 资源占用少很多。

不过现在 Firefox 也用默认多线程了,这个优势虽然还有一点,但也不算多了

所以找几个这之外的理由

  • 隐私,像比较 Chrome 这种商业公司搞出来的东西,Firefox 在隐私上面要优秀很多
  • 便捷,Google 账号同步比 Firefox 的账号同步困难不少
  • 为用户着想,至少不会像 Chrome 一样说搞广告屏蔽器就搞,说砍什么就砍

出于时间原因,没有能力给这几个理由找依据

如果你不相信我的话,那么关闭这个页面就好

Lilac Train Writeup

0 写在之前

应该是一场新手入门欢乐赛

打着也确实快乐,应该是我 CTF 比赛第一次做出 Oi 之外的题目

绝大多数知识点都在 CTF Wiki 上,剩下就是脑洞了

管他呢,mcfx txdy!

1 PWN

1 坤坤の地址

同志,用 Linux!

然后就是 nc 一把梭

$ nc 47.94.239.235 4001
welcome to [email protected]
Here is kunkun's address:
flag{zonghelou_714}

2 坤坤の唱

放进 IDA 去,一看,就是打开 $signer/$music,不允许你写 ../

然后 Hint 告诉你要访问 ../flag

然后就是傻逼题目了

nc 47.94.239.235 4002
input the singer's name:
..
input the song's name:
/flag
here is the lyric:
flag{w0w_you_successfully_escape_the_r3strict}

3 坤坤の石头剪刀布

打开一看,发现 rand() 函数的种子是 time()%10

那为什么要动脑子,写个种子是 0 的情况

试一下就行了

#include <cstdio>

int num = 0;

int myRand() {
    num = (num * num + 233) % 23333;
    return num;
}

void mySrand(unsigned int seed) {
    num = seed;
}

int playOnce() {
    fflush(stdout);

    int ai = myRand() % 3;

    if( ai == 0)
        return 1;
    if( ai == 1)
        return 2;
    if( ai == 2)
        return 0;
}

int main() {
    mySrand(1);
    int n = 100;
    while( n -- ) {
        printf( "%d\n", playOnce() );
    }
}

然后直接拿输出日服务器就行了

4 坤坤の篮球

题目给了二进制,大力 IDA

IDA 告诉我们 Hint,是根据 Target 位移出来的东西

简单的分析可以发现,基本上就是 8 位一截

然后写个程序大力草就行了

basket.cpp:

#include <cstdio>

#include <iostream>

int n;

int read() {
  int x = 0, w = 1; char ch = 0;
  while (ch < '0' || ch > '9') {  if (ch == '-') w = -1; ch = getchar(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
  return x * w;
}


int main() {
    while(1) {
        n = read();
        int u1 = ( 1 << 8 ) - 1;
        int tmp1 = n & u1;
        n >>= 8;
        int tmp2 = n & u1;
        n >>= 8;
        int tmp3 = n & u1;
        n >>= 8;
        int tmp4 = n & u1;

        int res = tmp1;
        res <<= 8;
        res |= tmp4;
        res <<= 8;
        res |= tmp2;
        res <<= 8;
        res |= tmp3;
        printf( "%d\n", res );
    }
}

//-1897606077
// 00011101110010011010100010000110./basket.run  0.00s user 0.00s system 0% cpu 2.026 total
// 
// Press ENTER or type command to continue
// 1133434084
// 10000111000111011010100111001000./basket.run  0.00s user 0.00s system 0% cpu 0.656 total
//
// 00011101 11001001 10101000 10000110
// 10000111 00011101 10101001 11001000
// 10001001 00011101 10101011 11000110

temp.py:

#!/usr/bin/python

from pwn import *

sh = process( './basket.o' )
rem = remote( "47.94.239.235", "4003" )

rem.recvline()
sh.sendline( rem.recvline() )
rem.sendline( sh.readline() )

for i in range (1,90):
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    print( rem.recvline() )
    sh.sendline( rem.recvline() )
    rem.sendline( sh.readline() )

rem.interactive()

事后发现基本上随便乱输入就可以得到 flag

毕竟是 pwn 题

5 坤坤のrap

放到 IDA,读入量比字符串定义的多

直接多放点就过去了

$ nc 47.94.239.235 4004
请开始你的表演:
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
ncongrats, here is the flag
flag{stack_0verflow_is_annoying!!}
tql!!!

6 坤坤の舞

和上面的题目一样,都有溢出的漏洞

执行 get_flag() 函数应该会输出 Flag

那 pwntool 直接草就行了

扩展阅读: 栈溢出原理 – CTF Wiki

7 坤坤の绝地反击

和上面一样,还是溢出,但是这次要带个参

然后我直接按普通堆做

全然没有注意开了 NX 保护…

后来给了个 Hint

那就是大力 ROP 搞就行了

扩展阅读: 基本 ROP – CTF Wiki

2 RE

1 basicre1

逐位 Xor 加密,直接解

2 basicre2

代码就是对着 char 瞎jb位移

然后倒推一下,输出,没了

当时写了个 cpp 还原的,找不到了,不过本来就是签到题,不管了

3 basicre3

代码注释里表明这是个算法

目测 TEA 及其变种

网上找个解密的,没了

4 babyre

IDA 后基本上可以发现这是个 RC4 加密算法

然而我赛后才发现

想个办法把里面东西倒出来

发现程序调用了 memcmp,LD_PRELOAD 可以套到目标密文

RC4 具有自反性,在把目标密文放进去,得到明文,也就是 Flag

5 hundred

赛后 mcfx 爷提醒是个数组,还是个巨大线性方程组

我拿 IDA 打开,然后得到了一大堆 if 包裹的条件判断

Vim 随便处理一下就可以变成 z3 的 solve 函数的参数

然后放到 z3 里跑就行了

如果直接用 .model() 输出会输出不全,手动 .model().eval()

脚本太大了,这里是链接:https://blog.woshiluo.com/wp-content/uploads/2020/05/libac_re5.zip

我怎么写的这么多行?

Vim 宏真好用

3 WEB

这次的 WEB 题相比较别的真的好欢乐…

1 F12

curl -v 或者直接 F12 看 Header

2 i18n

extract 会覆盖变量,考虑覆盖 language_file

没了

3 ezsql

签到题,payload 是 admin'#

4 ezsql again

查看页面原码,得到 login.php.bak

发现 SQL 注入可能性基本为 0

我们可以使 $dbpassnull

发现进来的 $password 没有验证,不传就行了

5 where is flag?

题目给了任意读,但是扬了 flag

可惜 file 被 open 了,我们可以在 procfs 里找到

但是我们并不知道 pid

所以用一个科技 /proc/self

没了

6 ez_bypass

感觉这个比上一道简单

  • php md5 碰撞
  • php == 符号不需要相等
  • json_decode 后面会覆盖前面的

构造一下

curl http://47.93.34.105:8081/\?s\=QNKCDZO\&t\=240610708 -d 'pw=20200501", "password": "shouhukunkun'

没了

7 是什么蒙蔽了你的双眼

我确实菜

对着题目给的参数 base64 -d 三次,得到 flag.jpg

猜测参数就是查询套三次 base64

然后试图获取 index.php

发现替换了非字母且非.为空
替换 config!

扫描 .index.php.swp

提示看 f1lllaggg!lilac.php

然后代码审计 f1lllaggg!lilac.php

要么 extract 魔改 t,要么直接传空 t 可以过非严格判断

所以那个链接是干什么的,迷惑

4 CRYPTO

这次的比赛激起了我对 Crypto 的兴趣

前五题都是工具题目,没啥说的

合理运用 CyberChef 和 Wikipedia 即可

6 单表替换

https://quipqiup.com/ 爆破即可

7 CH₃COOH

题目说是原题,直接拖 Google

实际上是 Vigenère 密码,和醋酸的英文名几乎一样

然后找个工具爆破就没了

8 三天之内

查看源码,发现使用 Unix 时间戳做密码

Unix 时间戳就那么多,写个爆破就行了

from Crypto.Cipher import AES
#from secret import flag
import time
from hashlib import md5
import base64

time = int(time.time())
while 1:
    time = time - 1
    key = md5(str(time).encode()).digest()
    aes = AES.new(key, AES.MODE_ECB)
    flag = base64.b64decode( 'THM3FOB7PxOgVoI1fGsqQDJLGu41mL9nKCNeMvXzB+l8MFirir0C19YRS/ruDILq')
    outData = aes.decrypt(flag)
    print(outData)

跑个 30s,在输出里搜索一下 flag 就行了

9 神必 base64

基本上就是 b64 变种

映射一下就行了

#include <cstdio>

char mp[1000];

int main() {
    FILE* qwq = fopen( "qwq", "r" );
    FILE* cip = fopen( "cipher.txt", "r" );
    char s1, s2;
    while( fscanf( qwq, "%c", &s1 ) !=EOF && fscanf( cip, "%c", &s2 ) ) {
        if( map[s1] != 0 ) 
            continue;
        mp[s1] = s2;
    }
    for( char a = 'A'; a <= 'Z'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    for( char a = 'a'; a <= 'z'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    for( char a = '0'; a <= '9'; a ++ ) {
        if( mp[a] == 0 )
            printf( "0" );
        printf( "%c", mp[a] );
    }
    printf( "%c", mp['+'] );
    printf( "%c", mp['/'] );
    printf( "%c", mp['='] );

}

10 RSA – 0

RSA 原理题

直接解就行了

11 RSA – 1

n 变成三个质数相乘了,但是不影响我们解密

import binascii
import gmpy

p = 252647779892687905173761792949656998433
q = 290615416181922737045361451171930371659
r = 281613259213037257262703439109757908501
n = p * q * r
e = 0x10001
# rased = pow(flag, e, n)
rsaed = 1169612223485519024207841670191078798101684935551461601922416127588930439758194701318838707953651437973827125265577

phi = ( p - 1 ) * ( q - 1 ) * ( r - 1 )
inv = gmpy.invert( e, phi )

print(inv)
print(hex(pow( rsaed, inv, n )))

小插曲,我本来手写的 exgcd 求逆元,结果写错了,最后因为不会 py 而选择了 gmpy

5 MISC

1 打工是不可能打工的

题目关于劳动法和基本法的什么东西就先略过了

大家都知道是怎么回事(

然后,StegSolve 直接 Frame 逐个看就行了

2 zip-0

题目说的是 9 位数字密码

这,不就是爆破

虽然事后发现 7zip 可以直接打开,惊了

据说是非预期的错误,笑了

3 zip-1

题目说了 010Editor

那就没什么说的了

4 樱花

strings

没了

5 隐写

仔细看,Red plane 0 左上角一段白

就选择 Red plane 0 通道,LSB 一下,就知道 Flag 了

6 真正的互联网

访问链接即可

7 zip-2

明文破解

pkcrack -c "lilac.png" -p lilac.png -C ./zip-2.zip -P ./lilac-logo.zip -d qwq.zip

没了

8 Yankee with no brim

binwalk 草出来里面的 png

发现 png 的 CRC 有问题

改个 Height,没了

9 大司马与千层饼

我先建议出题人司马

直接 OD 会有一句 You see the string,but it is not so easy...but it's baby! 来嘲讽你

总之 binwalk 套出里面的 7z,解压出来是个 gif,string 里面的 Flag 是 Fake

gif 逐帧草出来两个残缺二维码,补全,扫一下,结果还是 Fake

赛后有 Hint 告诉我们

「你在第二层,你以为他在第五层,实际上他在第一层」

你妈的,直接对 EXE Resource Hacker 得到一个凯撒密码

解出来是个网址,访问是个残缺二维码

补上定位点,扫就得到 Flag

6 Basic

没啥说的,签到

7 结

总之是一场相当快乐的比赛

几乎除了 Web 所有东西都是现学的,这大概就是在线比赛的乐趣吧,没有所谓记忆造成的堡垒

感谢举办方,给了我学习的机会

最后,跟我一起喊,mcfx 天下第一!

Fcitx5 & Rime 配置小记

输入过程截图
Fcitx5 输入截图

0 Rime 是什么

在很多情况下,如果你直接带着 Linux 输入法 这样的关键字去 Google 搜索

那么你得到的通常都是 Google Pinyin,或者 Sogou Pinyin

Google Pinyin 年久失修,Sogou 的话,维护也不算多上心

如果你再认真一点,你也许可以找到 Sunpinyin 和 Libpinyin

这两个的体验已经相当不错了,但你也会发现,在准确率上,还是差了点,而且在词库大的时候,还会很卡

这个时候,你就会查到 Rime —— 中州韵输入法引擎


聪明的输入法懂我心意

这是 Rime 自己的标语

Rime 具有更强大的定制性,更优秀的词语联想,以及跨平台的支持

如果你不相信 Sogou(相信我,没几个人相信 Sogou 不会上传你的数据),那么 Rime 是目前最优秀的选择

0.1 环境 & 我的需求

Arch Linux

小鹤双拼用户

1 Rime 的安装

对于 Arch Linux,我们首先需要选择一个输入平台,我选择的是 Fcitx5

关于 Fcitx5,你可以查阅 Fcitx5 – ArchWiki

(虽然这个东西在 Waylnd 下的功能还很残缺,但是,Wayland 本身问题也不少)

关于 Rime,Arch Wiki 有 这个页面

这个页面简单的介绍了 Rime 的安装方式与使用方式,不过并没有关于 Fcitx5 的介绍

所以我来简单的记录一下

1.1 Fcitx5 的安装

pacman -S fcitx5 fcitx5-qt fcitx5-gtk
pacman -S fcitx5-chinese-addons fcitx-rime

此时,Fcitx5 的配置文件在 ~/.config/fcitx5

1.2 Rime 的安装

pacman -S librime 
pacman -S rime-double-pinyin #需要双拼的话,安装这个

此时,Rime 的配置文件在 ~/.local/share/fcitx5/rime

1.3 Fcitx5 的配置

你可以选择使用 kcm-fcitx5 来通过 GUI 进行配置

不过本篇文章,我选择自己动手

注意:Fcitx5 在关闭的时候,会覆盖配置文件,所以请确保 Fcitx5 关闭后,再修改配置文件

$ cat ~/.config/fcitx5/profile 
[Groups/0]
# Group Name
Name=Default
# Layout
Default Layout=us
# Default Input Method
DefaultIM=rime

[Groups/0/Items/0]
# Name
Name=keyboard-us
# Layout
Layout=

[Groups/0/Items/1]
# Name
Name=rime
# Layout
Layout=

[GroupOrder]
0=Default

这份配置文件给 Fcitx5 设置了两个输入法,一个是 US 键盘,一个是 Rime

然后,和其他输入平台一样,我们需要配置环境变量

cat ~/.xprofile
export GTK_IM_MODULE=fcitx5
export [email protected]=fcitx5
export QT_IM_MODULE=fcitx5

这个是使用 Xorg 时才有效的

关于使用 Wayland 时的环境变量设置,请查阅 Environment variables (简体中文) – Arch Wiki

然后将 Fcitx5 加入自启动后,重启即可

2 Rime 的配置

2.0 安利时间

Github 上有许多优秀的 rime 的配置文件

通常情况下,你只需要将整个项目 clone 到本地,便可以直接使用

这里推荐 wongdean/rime-settings

以及,这也是一个不错 Rime 配置 https://sh.alynx.one/posts/My-RIME/

下面,就是我的折腾环节

2.1 极光拼音

明月拼音不是不香

就是每次在打词库里没有的词组的时候,经常会出现一堆繁体好几页,我还找不到自己想要的

这个问题显然是简体繁体之间转换除了什么奇怪的问题,不过,这个问题显然不好解决

既然解决不了,不如搞一个基于简体的输入方案

显然,不止我一个这么想

hosxy/rime-aurora-pinyin 就是这样一种输入方案,码表全部为简体中文,并且几乎只有 「通用规范汉字表」 中的汉字

然后你兴冲冲的下载了,开始用了,发现有一个问题

这个输入方案,没有词组……

2.2 寻找词库

通常情况下, Sogou 词库 里能找到我们需要的词库

但是这次不一样,这个输入方案里一点词库都没有

所以即使从 Sogou 词库里鼓捣几个下来,输入体验也不是很好

这个时候,我们需要一份中文常用词汇表

我找到了这个 indiejoseph/现代汉语常用词表.txt

简单处理一下(Vim 都可以处理),就可以用做 Rime 的词库了

再来试试,不错

2.3 Sogou 词库的导入

这个倒是有比较优秀的方案了 studyzy/imewlconverter

虽然 AUR 里有这个包,但是我并没有成功安装,反正 Releases 里也有 bin,直接用吧

3 结

本篇文章使用 Fcitx5 + Rime 在 Terminator + Vim 的环境下写的

在写这篇文章时,体验还是很好的,九成词语都在第一或者第二候选,不在的词语虽然需要自己去选,但并不复杂

本文所有配置文件都可以在 woshiluo/woshiluo-config 里找到

这次在写文章的时候主要参考是各个项目的 Readme 和 Wiki,以及 Arch Wiki,就不一一列出来了

这篇文章只是基于自己的配置经历所写,如果在任何地方有错误,希望你能通过评论指出

最后,安利 hosxy/fcitx5-material-color 主题,上面的截图就是这个主题,非常好看

i3wm 从初识到真香

本篇文章是一个配置案例,而并非入门指南

0 怎么认识的 i3wm

我一开始用 Linux 是 DDE 玩家(Deepin 对萌新及其友好),后来改用 Debian ,就开始当 Gnome 人了

Gnome 作为一个几乎开箱即用的桌面环境还是很不错的。后来也试用过 KDE,被复杂的控制劝退了,于是就一直用 Gnome

后来听机房的 c0per 学长说过 i3,不过在他 laptop 上的 i3wm 真的好简洁简陋,大概是一名高三生实在是没有时间,所以我也就没有在意过这个东西。

前两天又双遇到了 Gnome 的一堆 Bug,大概是每逢 Gnome 版本更新都有的,于是在 LK 的大力安利下入坑了

1 什么是 i3wm

「i3 是一种动态的平铺式窗口管理器」

ArchWiki – I3_(简体中文)

反正我是没有看懂这个简介,不过让我们顺着查一下

「平铺式(或直译瓦片式)窗口管理器,其中的窗口不能够重叠,而是像瓦片一样挨个摆放。这种窗口管理器一般比较依赖键盘操作,较少使用鼠标。此类窗口管理器一般也是高度可定制的。」

ArchWiki – Window_manager_(简体中文)

简单来讲,i3wm 作为一个窗口管理器,默认会将你的窗口像瓦片一样放置于屏幕上,但你也可以令其变成浮动窗口

i3wm 和 Gnome 最大的区别,是一个是 DE,一个是 WM,前者对后者实际上是包含关系

不过我在更换 i3wm 后并没有继续使用 gdm,而是使用了 LightDM

i3wm 有 i3bar,用于显示系统的信息等

2 配置

相比较 Gnome 的一套环境,i3wm 只是一个 WM,很多功能都要自己配置

所以在这里列了一些我使用 i3wm 的配置

2.1 快捷键

i3wm 有一个好,配置文件里几乎能改一切

i3wm 的快捷键都在 ~/.config/i3/config 写的很清楚

我个人并没有对快捷键做什么修改

2.2 i3status

i3status 作为 i3bar 的一部分,可以用于显示系统状态之类的

我在调 i3status 调了一阵后发现 —— 这东西太简洁了,想调好看很费事

于是我选择了 greshake/i3status-rust 作为了替代

并在 i3status 中调用了一言,有那么两句中二的话刺激一下自己也挺好的

2.3 rofi

i3 中默认使用 dmenu 作为执行命令的方式

但是这个东西相当简洁,甚至不支持快速切换窗口

但是我们有替代品 rofi

$ cat ~/.config/rofi/config.rasi
configuration {
    modi: "window,drun,ssh,combi";
    theme: "android_notification";
    font: "Fira Code 10";
    combi-modi: "window,drun,ssh";
}

然后在 i3 的配置文件中写入

bindsym $mod+d exec --no-startup-id "rofi -show combi"

2.4 acpi 配置

i3 并不会给你自动配置好 ACPI 事件, 不过这个很好处理,用 acpid 就可以了

2.5 自动锁屏/睡眠

xautolock DPMS 可以轻松的完成这个任务

i3lock 使用起来挺顺手的,我个人喜欢把背景图片加个毛玻璃效果当 i3lock 的壁纸,这个 gimp 里拿滤镜搞就行了

在 i3 的配置文件中写写入

exec --no-startup-id xset s 60 120
exec --no-startup-id xss-lock -n ~/.config/i3/i3lock.sh -- i3lock -n -i ~/Pictures/Wallpaper/71849322_p0_glur.png
exec --no-startup-id ~/.config/i3/screensaver.sh
exec --no-startup-id xautolock -time 5 -locker "systemctl suspend"
$ cat ~/.config/i3/i3lock.sh
#!/bin/sh

xset dpms force off

~/.config/i3/screensaver.shhttps://github.com/iye/lightsOn,用于避免在看视频的时候给 suspend 了

这个可以做到 60s 不动黑屏,180s 后开启 i3lock,300s 后 suspend

3 结

本文的所有配置都可以在 woshiluo/woshiluo-config 下找到

本文仅仅是自己配置的小小记录,如果有任何问题,请大佬在评论区指出

总的来说,i3 给我的感觉像极了 vim,配置文件坑半天,上手难度不小,不过上手了还是很爽的

反正给我的感觉比 Gnome 爽不少

虽然要自己配好多东西((

3.1 致谢

我在配置的时候参考了下面这些文章/网页,在此表达谢意

顺带 Orz LK

Codeforces Contest #1325 解题报告 & 题目大意

A EhAb AnD gCd

题目大意

给定一个整数 $x(2\leq x \leq 10^9)$

求 $a,b$ 满足 $\gcd(a,b) + \operatorname{lcm}(a,b) = x$

多组解输出任意一个

Code

这有啥说的,随便找个质因数让后输出 $p, x$ 就可以

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:36:48

#include <cmath>
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int t, x;

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &x );
        int sq = std::sqrt(x) + 1;
        for( int i = 1; i <= sq; i ++ ) {
            if( x % i == 0 ) {
                int tmp = ( x / i ) - 1;
                if( tmp == 0 )
                    continue;
                printf( "%d %d\n", i, tmp * i );
                break;
            }
        }
    }
}

B CopyCopyCopyCopyCopy

题目大意

给你一个长度为 $n$ 的数列 $a$, 现在你可以复制无数个 $a$ 接到原来的数列后面

问这样接完后,最长严格上升子序列的长度

Code

因为可以接无限次,所以直接输出数字个数就可以了

// Woshiluo Luo<[email protected]>
// 2020/03/14 22:42:47
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

int t;
int n;
int a[N];

int main() {
    scanf( "%d", &t );
    while( t -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        int cnt = 0, la = 0;
        for( int i = 1; i <= n; i ++ ) {
            if( i == 1 || a[i] != la ) {
                la = a[i];
                cnt ++;
            }
        }
        printf( "%d\n", cnt );
    }
}

C Ehab and Path-etic MEXs

题目大意

给一棵节点数为 $n$ 的树

现在你要给每条边一个边权,要求:

  • 边权为一个整数 $v(0\leq v \leq n – 2)$
  • 每条边的边权不能和别的边的相同

现在定义 $MEX(u,v)$ 为 $u,v$ 之间的最短简单路径上没有出现的边权中的最小值

请给出一种边权方案,最小化 $\max{MEX(u,v)}$

思路

考虑每条边会被算进去多少次,记为每条边的贡献

贡献越大给越大的边就可以了

实际上可以更加简化,因为无论如何一定有一个 $MEX \geq 2$

所以我们尽可能避免 $0,1,2$ 出现在一条边上即可

随便找一个度数 $\geq 2$ 的点,把这三个数字放上去即可

如果没有这种点,那么怎么摆都会有一条 $MEX=n-1$ 的路径

Code

// Woshiluo Luo<[email protected]>  
// 2020/03/14 22:52:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;

// Edge Start
struct edge {
    int to, next, val;
} e[ N << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to, int val ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    e[ecnt].val = val;
    ehead[now] = ecnt;
}
// Edge End

struct node { long long val; int id; } max[N];
bool cmp( node _a, node _b ) { return _a.val < _b.val; }

int n, x, y;
int son[N], val[N];

void dfs( int now, int la ) {
    son[now] = 1;
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == la )
            continue;
        dfs( e[i].to, now );
        son[now] += son[ e[i].to ];
        max[ e[i].val ].val = ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) );
    }
}

int main() {
#ifdef woshiluo
    freopen( "c.in", "r", stdin );
    freopen( "c.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1, u, v; i < n; i ++ ) {
        max[i].id = i;
        scanf( "%d%d", &u, &v );
        add_edge( u, v, i );
        add_edge( v, u, i );
    }

    dfs( 1, 0 );

    std::sort( max + 1, max + n, cmp );

    for( int i = 1; i < n; i ++ ) {
        val[ max[i].id ] = i - 1;
    }

    for( int i = 1; i < n; i ++ ) {
        printf( "%d\n", val[i] );
    }
}

D Ehab the Xorcist

给定两个整数 $u,v$ 求最短的数列 $a$ 满足

  • $$ \sum a = v $$
  • xor 和为 $u$

多解输出任意一个

无解输出 $-1$

题目大意

这题感觉的 C 简单啊

满足 $xor$ 容易,满足 $v$ 的话需要难度

考虑最后 $xor$ 的结果受每个二进制位的和的奇偶性影响

因此可以确定每一位的奇偶性

然后随便搞一下满足 $v$ 就可以了

Code

// Woshiluo Luo<[email protected]>
// 2020/03/14 23:39:20
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

unsigned long long u, v;
int bit_u[110], bit_less[110], bit_cnt[110];
std::vector<unsigned long long> ans;

inline void noans() {
    printf( "-1\n" );
    exit(0);
}

void to_bit( unsigned long long a, int bit[] ) {
    int cnt = 0;
    while( a ) {
        bit[ ++ cnt ] = a & 1;
        a >>= 1;
    }
}

int main() {
    scanf( "%llu%llu", &u, &v );
    if( v < u )
        noans();

    to_bit( v - u, bit_less );
    to_bit( u, bit_u );

    for( int i = 1; i <= 100; i ++ ) {
        bit_cnt[i] = bit_u[i];
    }
    int p = 64;
    int cnt = 0;
    while( p ) {
        bit_cnt[p] += ( cnt - ( cnt & 1 ) );
        cnt = cnt & 1;
        if( bit_less[p] )
            cnt ++;
        p --; cnt <<= 1;
    }

    if( cnt != 0 )
        noans();

    bool flag = true;
    while( flag ) {
        flag = false;
        unsigned long long out = 0;
        unsigned long long p = 1;
        for( int i = 1; i <= 64; i ++, p <<= 1 ) {
            if( bit_cnt[i] ) {
                out = out | p;
                bit_cnt[i] --;
                flag = true;
            }
        }
        if( flag )
            ans.push_back(out);
    }

    cnt = ans.size();
    printf( "%d\n", cnt );
    for( int i = 0; i < cnt; i ++ ) {
        printf( "%llu ", ans[i] );
    }

}

E Ehab’s REAL Number Theory Problem

题目大意

给你一个长度为 $n$ 的数列,保证数列中每个数字有不超过 $7$ 个因数

请求出最短的子序列,使子序列成绩为完全平方数

思路

这题比 F 题难吧…

首先由 保证数列中每个数字有不超过 $7$ 个因数 得每个数不会有超过两个 $1$ 和其本身以外的质因数

然后我们可以先把每个数里的完全平方数因子先除掉,因为这些不会对答案造成影响

这样下来每个数的因子只有 1 和其本身以及两个质因数(前提是这个数不是质数)

然后建图,如果这个数是质数,将其和 $1$ 连接,如过不是将其的两个质因数连接

剩下就是求最小环

Code

// Woshiluo Luo<[email protected]>
// 2020/03/15 22:08:53

#include <cmath>
#include <cstdio>
#include <cstring>

#include <queue>
#include <vector>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e6 + 1e4;
const int M = 1100;
const int INF = 0x3f3f3f3f;

int n, ans = INF;
int dis[N], fa[N];
bool marked[N], pool[N];

// Edge Start
struct edge {
    int cur, to, next;
} e[ N << 1 ];
int ehead[N], ecnt = 1;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].cur = now;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

int bfs( int st ) {
    memset( dis, INF, sizeof(dis) );
    memset( fa, 0, sizeof(fa) );
    std::queue<int> q;
    q.push(st); dis[st] = 0;
    while( !q.empty() ) {
        int cur = q.front(); q.pop();
        for( int i = ehead[cur]; i; i = e[i].next ) {
            if( e[i].to == fa[cur] )
                continue;

            if( dis[ e[i].to ] >= INF ) {
                fa[ e[i].to ] = cur;
                dis[ e[i].to ] = dis[cur] + 1;
                q.push( e[i].to );
            }
            else {
                return dis[cur] + dis[ e[i].to ] + 1;
            }
        }
    }
    return INF;
}

int main() {
    scanf( "%d", &n );
    for( int i = 1, x; i <= n; i ++ ) {
        scanf( "%d", &x );
        std::vector<int> a;
        int cnt = std::sqrt(x) + 1;
        while(cnt > 1) {
            int cnt_pow = cnt * cnt;
            while( x % cnt_pow == 0 )
                x /= cnt_pow;
            cnt --;
        }
        if( x == 1 )
            chk_Min( ans, 1 );
        if( pool[x] )
            chk_Min( ans, 2 );
        pool[x] = true;
        int tmp = std::sqrt(x);
        for( int j = 2; j <= tmp; j ++ ) {
            if( x % j == 0 ) {
                a.push_back(j);
                a.push_back( x / j );
                break;
            }
        }
        if( a.size() == 0 ) {
            add_edge( 1, x );
            add_edge( x, 1 );
        }
        else if( a.size() != 0 ) {
            add_edge( a[0], a[1] );
            add_edge( a[1], a[0] );
        }
    }

    if( ans != INF ) {
        printf( "%d\n", ans );
        return 0;
    }

    for( int i = 1; i <= 1000; i ++ ) {
        if( ehead[i] )
            chk_Min( ans, bfs(i) );
    }

    if( ans >= INF )
        ans = -1;

    printf( "%d\n", ans );
}

F Ehab’s Last Theorem

题目大意

给定一个 $n$ 个节点的图

令 $glo=\lceil\sqrt{n}\rceil$

你要么找到一个长度和 $glo$ 相等的环

要么找到一个比 $glo$ 小的独立集

Code

先试图找环,找不到肯定有独立集

// Woshiluo Luo<[email protected]>  
// 2020/03/15 15:49:32
#include <cstdio>
#include <cstring>

#include <stack>
#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 1e5 + 1e4;
const int M = 2e5 + 1e4;

int n, m, need;

int dep[N];
bool vis[N];
std::stack<int> st;

// Edge Start
struct edge { int to, next; } e[ M << 1 ];
int ehead[N], ecnt;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End


void dfs( int now ) {
    st.push(now);
    dep[now] = st.size();
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( dep[ e[i].to ] == 0 )
            dfs( e[i].to );
        else if( dep[now] - dep[ e[i].to ] + 1 >= need ) {
            int size = dep[now] - dep[ e[i].to ] + 1;
            printf( "%d\n%d\n", 2, size );
            for( int i = 1; i <= size; i ++ ) {
                printf( "%d ", st.top() );
                st.pop();
            }
            exit(0);
        }
    }
    if( !vis[now] ) {
        for( int i = ehead[now]; i; i = e[i].next ) {
            vis[ e[i].to ] = true;
        }
    }
    st.pop();
}

int main() {
#ifdef woshiluo
    freopen( "f.in", "r", stdin );
    freopen( "f.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    while( need * need < n )
        need ++;

    while( m -- ) {
        int u, v;
        scanf( "%d%d", &u, &v );
        add_edge( u, v ); add_edge( v, u );
    }

    dfs(1);

    printf( "%d\n", 1 );
    int cnt = 0;
    for( int i = 1; i <= n; i ++ ) {
        if( vis[i] == false ) {
            printf( "%d ", i );
            cnt ++;
        }
        if( cnt == need )
            break;
    }
}

Codeforces Contest #1312 解题报告 & 部分翻译

比赛链接:Educational Codeforces Round 83 (Rated for Div. 2)

A Two Regular Polygons

1 题目大意

给你两个正多边形,一个 $n$ 条边 $A$ ,一个 $m$ 条边 $B$

问 $B$ 有没有可能被 $A$ 包含且所有顶点都与 $A$ 的某一个节点重合

有输出 YES ,否则输出 NO

2 Code

判 $n \bmod m = 0$ 就可以了

#include <cstdio>

int T;
int n, m;

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d%d", &n, &m );
        printf( "%s\n", ( n % m == 0 )? "YES": "NO" );
    }
}

B Bogosort

1 题目大意

给你一个长度为 $n$ 的序列 $a$, 你可以将 $a$ 重新排序,使其满足 $j – a_j \neq i – a_i$

输出任何一个即可

保证有解

$n \leq 100$

2 思路

$$
\begin{aligned}
j – a_j & \neq i – a_i \\
j – i & \neq a_j – a_i
\end{aligned}
$$

直接从大到小输出

3 Code

// Woshiluo Luo<[email protected]>  
// 2020/03/09 22:40:32 
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
int a[N];

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d", &n );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%d", &a[i] );
        }
        std::sort( a + 1, a + n + 1 );
        for( int i = n; i >= 1; i -- ) {
            printf( "%d ", a[i] );
        }
        printf( "\n" );
    }
}

C Adding Powers

1 题目大意

给你两个长度为 $n$ 的数列 $a,v$

其中 $a$ 通过输入提供,$v$ 初始所有值为 $0$

接下来,对于第 $i$ 次操作(从 $0$ 计数),你可以

  • 选择任意一个 $v_i$ 增加 $k^i$
  • 什么都不做

问你是否通过多次操作后,使 $v$ 变成 $a$

能输出 YES ,否则输出 NO

2 思路

首先对于每个数字 $a$, 考虑其是否可以变成多个 $k^i$ 的和(不能有重复的 $i$)

能的话算出来,看看有没有和之前重复的,有就不可能

不能的话直接没有可能

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 22:58:45
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 110;

int T;
int n;
long long k;
bool vis[N];
long long a[N];

inline void wrong() {
    printf( "NO\n" );
}

inline void right() {
    printf( "YES\n" );
}

void calc() {
    for( int i = 1; i <= n; i ++ ) {
        if( a[i] == 0 ) {
            continue;
        }
        long long cur = a[i];
        int cnt = 1;
        while( cur ) {
            int tmp = cur % k;
            if( tmp > 1 ) {
                wrong();
                return ;
            }
            if( tmp == 1 ) {
                if( vis[cnt] == false )
                    vis[cnt] = true;
                else {
                    wrong();
                    return ;
                }
            }
            cur /= k;
            cnt ++;
        }
    }
    right();
}

int main() {
    scanf( "%d", &T );
    while( T -- ) {
        memset( vis, 0, sizeof(vis) );

        scanf( "%d%lld", &n, &k );
        for( int i = 1; i <= n; i ++ ) {
            scanf( "%lld", &a[i] );
        }

        calc();
    }
}

D Count the Arrays

1 题目大意

你需要寻找这样的数列个数

  • 有 $n$ 个元素
  • 每个数字都是 $1$ 到 $m$ 之间的整数
  • 只有恰好一对数字相等
  • 数列先严格递增,再严格递减

个数对 $998244353$ 取模后输出

$2 \leq n \leq m \leq 2 \times 10^5$

2 思路

式子题,看 Code 去

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/09 23:21:18
#include <cstdio>
#include <cstring>

#include <algorithm>

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

const int N = 2e5 + 1e4;
const int mod = 998244353;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while(p) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}

inline int get_inv( int a ) { return ksm( a, mod - 2 ); }

int n, m, sum, ans;
int fact[N], inv[N];

void init() {
    fact[1] = 1;
    for( int i = 2; i <= m; i ++ ) {
        fact[i] = mul( fact[ i - 1 ], i );
    }
    inv[m] = get_inv( fact[m] );
    for( int i = m - 1; i >= 1; i -- ) {
        inv[i] = mul( inv[ i + 1 ], i + 1 );
    }
    inv[0] = 1;
    fact[0] = 1;
}

// Get C^a_b
inline int C( int a, int b ) {
    if( a <= 0 )
        return 1;
    if( b <= 0 )
        return 1;
    return mul( mul( fact[b], inv[ b - a ] ), inv[a] );
}

int main() {
#ifdef woshiluo
    freopen( "d.in", "r", stdin );
    freopen( "d.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    init();

    for( int i = n - 1; i <= m; i ++ ) {
        add_eq( sum, mul( C( n - 3, i - 2 ), mul( m - i + 1, n - 2 ) ) );
    }

    for( int i = 2; i < n; i ++ ) {
        add_eq( ans, mul( sum, C( i - 2, n - 3 ) ) );
    }

    printf( "%d\n", ans );
}

E Array Shrinking

1 题目大意

这好像是个原题

给你一个长度为 $n$ 的数列 $a$

如果 $a_i = a_{i + 1}$, 那么这两个数可以合并成 $a_i + 1$

问最小数列长度

$1 \leq a_i \leq 1000, 1 \leq n \leq 500$

2 思路

区间 dp

设 $f_{i,j}$ 为 $i$ 到 $j$ 最小长度

$merged_{i,j}$ 为 $i$ 到 $j$ 合并出来的数字

然后就是标准板子了

3 Code

// Woshiluo Luo<[email protected]>
// 2020/03/10 15:50:48
#include <cstdio>
#include <cstring>

#include <algorithm>

const int N = 510;

template<class T>
T Min( T _a, T _b ) { return _a < _b? _a: _b; }
template<class T>
T Max( T _a, T _b ) { return _a > _b? _a: _b; }
template<class T>
T chk_Min( T &_a, T _b ) { return _a = (_a < _b? _a: _b); }
template<class T>
T chk_Max( T &_a, T _b ) { return _a = (_a > _b? _a: _b); }

int n;
int a[N];
int f[N][N], merged[N][N];

int main() {
#ifdef woshiluo
    freopen( "e.in", "r", stdin );
    freopen( "e.out", "w", stdout );
#endif
    scanf( "%d", &n );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%d", &a[i] );
        f[i][i] = 1;
        merged[i][i] = a[i];
    }
    for( int len = 2; len <= n; len ++ ) {
        for( int left = 1, rig = len; rig <= n; left ++, rig ++ ) {
            f[left][rig] = rig - left + 1;
            for( int mid = left; mid < rig; mid ++ ) {
                int &f_left = f[left][mid], &f_rig = f[ mid + 1 ][rig],
                &merge_left = merged[left][mid], &merge_rig = merged[ mid + 1 ][rig];
                chk_Min( f[left][rig], f_left + f_rig );
                if( f_left == 1 && f_rig == 1 && merge_left == merge_rig ) {
                    f[left][rig] = 1;
                    merged[left][rig] = merge_left + 1;
                }
            }
        }
    }
    printf( "%d\n", f[1][n] );
}

AGC 034 F RNG and XOR

题目连接: https://atcoder.jp/contests/agc034/tasks/agc034_f

道理我都懂,可是不看题解不到啊……

$$\newcommand \xor{\mathbin{\mathbf{xor}}}$$

1 题意

给定一个数字 $n$

对于 $0 \cdots 2^n – 1$ 中每个数字都有一个 $a_i$

现在有一个数 $X$, 一开始为 $0$

每一次操作会随机选择一个数字 $i$ (其中 $0 \leq i \leq 2^n – 1$,选中 $i$ 的概率为 $\frac{a_i}{\sum a}$)

然后令 $X = X \xor i$

问使 $X=i$ 的期望次数

2 思路

先令
$$p_i=\frac{a_i}{\sum a}$$

令 $f_i$ 表示从 $i$ 到 $0$ 的期望次数,这和从 $0$ 到 $i$ 显然是一样的

接着有一个非常显然的式子

$$
\begin{aligned}
f_i &= f_{i \xor j} \times p_j + 1 ( i \neq 0 )\\
f_i – 1 &= f_{i \xor j } \times p_j ( i \neq 0 )
\end{aligned}
$$

然后我们就可以得到这个式子

$$ (f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( x, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} – 1 ) $$

但是 $x$ 是未知的

注意到 $\sum p = 1$ 所以左边右边的和是相等的

所以
$$
\begin{aligned}
x &= \sum_{i=0}^{2^n-1} f_i – \sum_{i=1}^{2^n-1} f_i – 1 \\
&= f_0 + 2^n – 1
\end{aligned}
$$

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
= ( f_0 + 2^n – 1, f_1 – 1, f_2 – 1, \cdots, f_{2^{n-1}} – 1, f_{2^n-1} -1 )
$$

我们需要的使其中两个式子没有未知数

注意到如果使 $p_0 = p_0 – 1$

那么右边每一个数都会减去 $f_i$

$$
(f_0, f_1, f_2, \cdots, f_{2^{n-1}}, f_{2^n-1}) \xor (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\ = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
$$

于是就可以放进 FWT 里直接做

然后你就发现这东西跑出来是错的……

为什么呢


$$
\begin{aligned}
\mathbf{P} & = (p_0 – 1, p_1, p_2, \dots, p_{2^{n-1}}, p_{2^n}) \\
\mathbf{A} & = ( 2^n – 1, – 1, – 1, \cdots, -1, -1 )
\end{aligned}
$$

因为 $\mathbf{P}$ 和 $\mathbf{A}$ FWT 后第一位都是 $0$

没有办法倒推出来 $f_0$

但是可以发现 $f$ 的值是可以平移的

$$ f_i + k = \sum_{i=0}^{2^n-1} p_j(f_{i \xor j} + k) + 1 = \sum_{i=0}^{2^n-1} f_{i \xor j} \times p_j + k + 1 $$

那么我们又知道 $f_i = 0$

所以将 $f$ 每一位都减去 $f_0$ 即可

3 Code

#include <cstdio> 

const int N = 1 << 20;
const int mod = 998244353;

int n;
int a[N], b[N], p[N], sum;

inline int add( int a, int b ) { return ( a + b ) % mod; }
inline int mul( int a, int b ) { return ( 1LL * a * b ) % mod; }
inline void add_eq( int &a, int b ) { a = ( a + b ) % mod; }
inline void mul_eq( int &a, int b ) { a = ( 1LL * a * b ) % mod; }

int ksm( int a, int p ) {
    int res = 1;
    while( p ) {
        if( p & 1 )
            res = mul( res, a );
        a = mul( a, a );
        p >>= 1;
    }
    return res;
}
inline int inv( int a ) { return ksm( a, mod - 2 ); }

void XOR( int *f, int len, int x = 1 ) {
    for( int o = 2, k = 1; o <= len; o <<= 1, k <<= 1 ) {
        for( int i = 0; i < len; i += o ) {
            for( int j = 0; j < k; j ++ ) {
                add_eq( f[ i + j ], f[ i + j + k ] );
                f[ i + j + k ] = add( f[ i + j ], add( - f[ i + j + k ], - f[ i + j + k ] ) );
                mul_eq( f[ i + j ], x ); mul_eq( f[ i + j + k ], x );
            }
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "F.in", "r", stdin );
    freopen( "F.out", "w", stdout );
#endif
    scanf( "%d", &n );
    n = 1 << n;
    for( int i = 0; i < n; i ++ ) {
        scanf( "%d", &a[i] );
        sum += a[i];
        b[i] = mod - 1;
    }
    sum = inv(sum);
    for( int i = 0; i < n; i ++ ) {
        p[i] = mul( a[i], sum );
    }

    b[0] = n - 1; p[0] -= 1;
    XOR( b, n ); XOR( p, n );
    for( int i = 0; i < n; i ++ ){
        mul_eq( b[i], inv( p[i] ) );
    }
    XOR( b, n, inv(2) );
    for( int i = 0; i < n; i ++ ) {
        printf( "%d\n", ( ( add( b[i], -b[0] ) + mod ) % mod ) );
    }
}