lxx 发布的文章

快速沃尔什变换(FWT)讲解 解决集合卷积的方法


能看到这篇博客的人,一定知道FWT是干什么的。(什么?你不知道?)
没事,这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了,那么恭喜你。如果你跟我一样看不懂,那么请继续往下看。

这里的A和B都是什么呢?其实它们是一个多维的向量(如果你不知道向量是什么,就把它当成数组),下标从0开始。
其中,$ A = <a_{0},a_{1},...,a_{2^{k}-1}> $,$ B = <b_{0},b_{1},...,b_{2^{k}-1}> $,$ C = A\otimes B $
这里我们定义$$ A\pm B = < a_{0}\pm b_{0}, a_{1}\pm b_{1},..., (a_{2^{k}-1})\pm (b_{2^{k}-1}) > $$ 即对应位相加(减)$$ A * B = < a_{0} * b_{0}, a_{1} * b_{1},..., (a_{2^{k}-1}) * (b_{2^{k}-1}) > $$即对应位相乘$ A\otimes B $ 为A和B做卷积之后得到的结果,也是一个和原来大小一样的向量。

注意到FWT做的是二进制上的位运算,所以一定要把A和B补到2的整次幂次(即不足的地方填上0)。

我们要构造一个变换tf,使得$tf(A)*tf(B)=tf(C)$。这个变换的对象是一个大小为$2^{k}$的向量,变换出来的结果也是一个大小为$2^{k}$的向量。

就以异或举例。picks告诉我们$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$A_{0}=<a_{0},a_{1},...,a_{2^{k-1}-1}>$$$$A_{1}=<a_{2^{k-1}},a_{2^{k-1}+1},...,a_{2^{k}-1}>$$即把A中的下标按照二进制最高位为0或1分成前后两部分(前面的为$A_{0}$,后面的为$A_{1}$),分治下去做。

分治之后得到$tf(A_{0})$和$tf(A_{1})$。然后tf(A)的前半部分(即$[0,2^{k-1}-1]$)为$tf(A_{0})+tf(A_{1})$,后半部分(即$[2^{k-1},2^{k}-1]$)为$tf(A_{0})-tf(A_{1})$。(其实就是已知两个向量,把两个向量做加减运算,加的那个结果填到前一半中,减的那个结果填到后一半中)。

然而,这为什么是对的?
接下来我们来证明它是对的。

我要事先说明(注意不是证明)一个引理:$tf(A+B)=tf(A)+tf(B)$。这个东西看上去挺直观的(一点都不直观好吗。。)。这个东西可以用数学归纳法证。这里略过。。。(有时间的时候再补上)

我们看k=1的时候。根据定义,有$$tf(A)=<a_{0}+a_{1},a_{0}-a_{1}>$$$$tf(B)=<b_{0}+b_{1},b_{0}-b_{1}>$$$$tf(C)=<c_{0}+c_{1},c_{0}-c_{1}>$$$$c_{0}=a_{0}*b_{0}+a_{1}*b_{1},c_{1}=a_{0}*b_{1}+a_{1}*b_{0}$$自己代代看,反正代出来很神奇的的发现$tf(A)*tf(B)=tf(C)$

接下来使用数学归纳法。假设对于大小都为$2^{k}(k\epsilon N)$的向量A和B,满足$C = A\otimes B$,并且$tf(A)*tf(B)=tf(C)$。
考虑当大小为$2^{k+1}$的情况。我们要证明在这种情况下,$tf(A)*tf(B)=tf(C)$。根据定义,有
$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$tf(B)=(tf(B_{0})+tf(B_{1}),tf(B_{0})-tf(B_{1}))$$$$tf(A)*tf(B)=([tf(A_{0})+tf(A_{1})]*[tf(B_{0})+tf(B_{1})],[tf(A_{0})-tf(A_{1})]*[tf(B_{0})-tf(B_{1})])$$
暴力把式子拆开,有
$tf(A)*tf(B)=$
$$(tf(A_{0})*tf(B_{0})+tf(A_{0})*tf(B_{1})+tf(A_{1})*tf(B_{0})+tf(A_{1})*tf(B_{1}),$$$$tf(A_{0})*tf(B_{0})+tf(A_{1})*tf(B_{1})-tf(A_{0})*tf(B_{1})-tf(A_{1})*tf(B_{0}))$$
注意到这里的$A_{0}$,$A_{1}$,$B_{0}$,$B_{1}$都是大小为$2^{k}$的向量,符合归纳的基础。于是,
$tf(A)*tf(B)=$
$$(tf(A_{0}\otimes B_{0})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0})+tf(A_{1}\otimes B_{1}),$$$$tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$
由于异或每一位是独立,而这里如果我们把C按照最高位为0或1分成两部分,最高位的异或和其它位不相关。
于是有$$C=(C_{0},C_{1})=(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$
要证的等式
$$右边=tf(C)=tf(C_{0},C_{1})$$$$=tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$$$=(tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}))$$$$=(tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$$$=tf(A)*tf(B)=左边$$
至此,证毕。

然而这只是一个tf,还有一个逆变换utf。这个逆变换的正确性可以用同样的方法证明,即先看k=1的情况,然后一步一步用数归推上去。
证明方法比较简单(真的很简单),这里略过。

至于其它位运算,其证明方法与异或一致,这里不赘述。

说了这么多,其实这个证明并没有什么卵用(只是使得自己相信它是对的)。。大家还是背代码吧。。。

看完的找个模板题练练手感受一下吧,CSU 1911 Card Game

模板

// 题目要求取模时使用mod,否则去除mod
void FWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x - y + mod) % mod;
                // xor: a[i+j]=x+y, a[i+j+d]=x-y;
                // and: a[i+j]=x+y;
                // or: a[i+j+d]=x+y;
            }
        }
    }
}
void UFWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = 1LL * (x + y) * rev % mod;
                a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
                // xor: a[i+j]=(x+y)/2, a[i+j+d]=(x-y)/2;
                // and: a[i+j]=x-y;
                // or: a[i+j+d]=y-x;
            }
        }
    }
}
void solve(int a[], int b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % mod;
    }
    UFWT(a, n);
}

docker一键部署typecho博客网站


首先下载附件上传到服务器目录

使用脚本安装docker

#确保 yum 包更新到最新
sudo yum update

#执行 Docker 安装脚本,执行这个脚本会添加 docker.repo 源并安装 Docker。
curl -fsSL https://get.docker.com/ | sh

#启动 Docker 进程
sudo service docker start

#验证 docker 是否安装成功并在容器中执行一个测试的镜像
sudo docker run hello-world

设置docker开机自启动

sudo systemctl enable docker

安装docker compose

# 下载最新版本的 docker-compose 到 /usr/bin 目录下
curl -L https://github.com/docker/compose/releases/download/1.25.5/docker-compose-`uname -s`-`uname -m` -o /usr/bin/docker-compose

# 给 docker-compose 授权
chmod +x /usr/bin/docker-compose

下载typecho

下载到当前目录,解压到typecho文件夹
修改typecho.conf中的server_name为具体的域名
mysql.env中配置,具体详见mysql.env即可
进入php文件夹,执行docker build -t scofieldpeng/php-fpm:7.2.3-fpm .
返回项目根目录,然后执行docker-compose up -d即可
在宿主机的nginx中新建相应的配置文件,proxy到8080即可
初始化typecho配置
使用HTTPS
由于是采用的proxy到容器的80端口,因此typecho不会知道目前是用的https协议,通过源码可以看到,typecho支持显性告诉当前的域名是https,因此可以在typecho的index.php或者config.inc.php中添加下列代码:

开启https支持

define('__TYPECHO_SECURE__',TRUE);
当然,如果你的服务器只需要跑一个博客,而不需要其他的服务在80或者443端口,直接修改typecho.conf,添加https,再修改docker-compose.yaml文件,暴露出80和443端口即可,这里不做详细阐述。

备份和恢复/迁移

备份很简单,直接将项目目录整个copy下来即可,恢复时整个文件夹上传到新的服务器,然后进入目录执行docker-compose up -d重新跑起来即可,方便快捷

mysql管理

可以看到docker-compose中mysql镜像时暴露出了3306端口到127.0.0.1,可以通过ssh代理登录3306端口进行管理,也可以安装一个phpadmin的容器连接上,看自己方便啦!

一键部署附件
docker-typecho-master.rar


typecho博客网站更换域名


登录 MySQL 执行:
注意:以下 SQL 语句使用默认表前缀 typecho_,操作数据库前建议备份。


# 修改网站设置里的域名:
UPDATE `typecho_options` SET `value` = '新域名' WHERE `typecho_options`.`name` = 'siteUrl' AND `typecho_options`.`user` =0;

# 替换文章的域名
UPDATE `typecho_contents` SET `text` = REPLACE(`text`,'原域名','新域名');

# 将管理员的个人网站进行替换
UPDATE `typecho_users` SET `url` = REPLACE(`url`,'原域名','新域名');

# 替换评论中的域名
UPDATE `typecho_comments` SET `url` = REPLACE(`url`,'原域名','新域名');
UPDATE `typecho_comments` SET `text` = REPLACE(`text`,'原域名','新域名');
```sql

docker一键部署wordpress


使用脚本安装docker

#确保 yum 包更新到最新
sudo yum update

#执行 Docker 安装脚本,执行这个脚本会添加 docker.repo 源并安装 Docker。
curl -fsSL https://get.docker.com/ | sh

#启动 Docker 进程
sudo service docker start

#验证 docker 是否安装成功并在容器中执行一个测试的镜像
sudo docker run hello-world

设置docker开机自启动

sudo systemctl enable docker

安装docker compose

# 下载最新版本的 docker-compose 到 /usr/bin 目录下
curl -L https://github.com/docker/compose/releases/download/1.25.5/docker-compose-`uname -s`-`uname -m` -o /usr/bin/docker-compose

# 给 docker-compose 授权
chmod +x /usr/bin/docker-compose

编写docker-compose.yml

version: '3'
services:
  db:
    image: mysql:5.7
    volumes:
      - db_data:/var/lib/mysql
    restart: always
    environment:
      MYSQL_ROOT_PASSWORD: somewordpress
      MYSQL_DATABASE: wordpress
      MYSQL_USER: wordpress
      MYSQL_PASSWORD: wordpress
    ports:
      - "3306:3306"
  wordpress:
    depends_on:
      - db
    image: wordpress:latest
    volumes:
      - wp_site:/var/www/html
    ports:
      - "80:80"
      - "443:443"
    restart: always
    environment:
      WORDPRESS_DB_HOST: db:3306
      WORDPRESS_DB_USER: wordpress
      WORDPRESS_DB_PASSWORD: wordpress
volumes:
  db_data:
  wp_site:
```bash

##启动wordpress
```bash
docker-compose up -d

centos如何升级gcc


升级gcc的一个更加简单的做法,但是这个做法的缺点是只支持64位程序而无32位支持。

采用CentOS的一个第三方库SCL(软件选集),SCL可以在不覆盖原系统软件包的情况下安装新的软件包与老软件包共存并且可以使用scl命令切换,不过也有个缺点就是只支持64位的。还有devtoolset-4(gcc 5.2)及之前的版本都已经结束支持,只能通过其他方法安装。

本次升级到gcc8,命令如下:


yum -y install centos-release-scl
yum -y install devtoolset-8-gcc devtoolset-8-gcc-c++ devtoolset-8-binutils
scl enable devtoolset-8 bash  #启动gcc8
```bash

  你要哪个版本的就把第2条命令中的数字8改成你要的主版本号就可以了。这样升级到的是最新的版本。例如8升级到的是8.2.0而不是8.1。

  通过scl命令启动gcc,这个只是暂时的,当你的shell关闭后或者重启就会恢复原来的版本,要想一直使用升级后的版本可以使用如下命令:

```bash
echo "source /opt/rh/devtoolset-8/enable" >>/etc/profile
```bash