2023年3月

〇、简介

1、DES 简介

DES 全称为 Data Encryption Standard,即数据加密标准,是一种使用密钥加密的块算法,1977 年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),并授权在非密级政府通信中使用,随后该算法在国际上广泛流传开来。

在很长时间内,许多人心目中“密码生成”与 DES 一直是个同义词。直到 1997 年 NIST(美国国家标准与技术研究院)开始公开征集更安全的加密算法以替代 DES,并在 2001 年推出了更加安全的 AES(Advanced Encryption Standard)高级加密标准。

优点:

  • Feistel 网络的轮数可以任意增加;
  • 解密与轮函数 f 无关,轮函数f也不需要有逆函数;
  • 轮函数可以设计得足够复杂;
  • 加密和解密可以使用完全相同的结构来实现。

缺点:

  • 分组比较短;
  • 密钥太短;
  • 密码生命周期短;
  • 运算速度较慢。

2、3DES 简介

其实并不是直接由 DES 过渡到 AES,还有一个 3DES 统治时期。3DES 也称 Triple DES,它使用 3 条 56 位的密钥对数据进行三次加密。

3DES 算法通过对 DES 算法进行改进,增加 DES 的密钥长度来避免类似的攻击,针对每个数据块进行三次 DES 加密;因此,3DES 加密算法并非什么新的加密算法,是 DES 的一个更安全的变形,它以 DES 为基本模块,通过组合分组方法设计出分组加密算法。

相比 DES,
3DES 因密钥长度变长,安全性有所提高,但其处理速度不高
。因此又出现了 AES 加密算法,AES 较于 3DES 速度更快、安全性也更高。

加密:

  • 为了兼容普通的 DES,3DES 并没有直接使用 加密->加密->加密 的方式,而是采用了
    加密->解密->加密
    的方式。
  • 当三重密钥均相同时,前两步相互抵消,相当于仅实现了一次加密
    ,因此可实现对普通 DES 加密算法的兼容。

解密:

  • 3DES 解密过程,与加密过程相反,即逆序使用密钥。是以密钥 3、密钥 2、密钥 1的顺序执行
    解密->加密->解密

一、C# 代码实现

1、DES

// 测试(密钥需要是八位字符)
string jiamihou = DesEncrypt("TestString", "66666611222", false); // 57fe567eaa866373f851a526f07d9e26
string jiamiqian = DesDecrypt(jiamihou32, "66666611222");
/// <summary>
/// DES加密字符串
/// </summary>
/// <param name="deseninstr">待加密的字符串</param>
/// <param name="deskey">加密密钥,要求为8位</param>
/// <param name="isupper">返回大写密文,false:小写</param>
/// <returns>加密成功返回加密后的字符串,失败返回源串</returns>
public static string DesEncrypt(string deseninstr, string deskey, bool isupper = true)
{
    StringBuilder stringBuilder = new StringBuilder();
    try
    {
        DESCryptoServiceProvider des = new DESCryptoServiceProvider();
        byte[] inputByteArray = Encoding.UTF8.GetBytes(deseninstr);
        des.Key = Encoding.UTF8.GetBytes(deskey);
        des.IV = Encoding.UTF8.GetBytes(deskey); // 当 mode 为 CBC 时,偏移量必传
        des.Mode=CipherMode.ECB; // 为空默认 CBC
        MemoryStream memoryStream = new MemoryStream();
        CryptoStream cryptoStream = new CryptoStream(memoryStream, des.CreateEncryptor(), CryptoStreamMode.Write);
        cryptoStream.Write(inputByteArray, 0, inputByteArray.Length);
        cryptoStream.FlushFinalBlock();
        foreach (byte bb in memoryStream.ToArray())
        {
            stringBuilder.AppendFormat(isupper ? "{0:X2}" : "{0:x2}", bb);
        }
        return stringBuilder.ToString();
    }
    catch (Exception ex)
    {
        return deseninstr;
    }
}
/// <summary>
/// DES解密字符串
/// </summary>
/// <param name="desdeinstr">待解密的字符串</param>
/// <param name="deskey">解密密钥,要求为8位</param>
/// <returns>解密成功返回解密后的字符串,失败返源串</returns>
public static string DesDecrypt(string desdeinstr, string deskey)
{
    MemoryStream memoryStream = new MemoryStream();
    try
    {
        DESCryptoServiceProvider des = new DESCryptoServiceProvider();
        byte[] inputByteArray = new byte[desdeinstr.Length / 2];
        for (int ii = 0; ii < desdeinstr.Length / 2; ii++)
        {
            int intt = (Convert.ToInt32(desdeinstr.Substring(ii * 2, 2), 16));
            inputByteArray[ii] = (byte)intt;
        }
        des.Key = Encoding.UTF8.GetBytes(deskey);
        des.IV = Encoding.UTF8.GetBytes(deskey); // 当 mode 为 CBC 时,偏移量必传
        des.Mode = CipherMode.ECB; // 为空默认 CBC
        CryptoStream cs = new CryptoStream(memoryStream, des.CreateDecryptor(), CryptoStreamMode.Write);
        cs.Write(inputByteArray, 0, inputByteArray.Length);
        cs.FlushFinalBlock();
        return Encoding.UTF8.GetString(memoryStream.ToArray());
    }
    catch
    {
        return desdeinstr;
    }
}

2、3DES

密文采用 Base64 格式输出。

疑问解答:三次加解密操作会运用三个不同的 Key,但是我们只传入了一个密钥,怎么回事?

3DES 密钥必须为 24 位,为 DES 的 3 倍,经测试得出结论:

  • TripleDESCryptoServiceProvider 内部将密钥分成 3 份,进行了加密解密三重操作。
  • 我们把 24 位字符串分成三部分,如果三部分均相等,或前两部分相等,就会报错:"Specified key is a known weak key for 'TripleDES' and cannot be used."--指定的密钥是'TripleDES'的已知弱密钥,不能使用。
// 测试
string jiamihou16 = SecurityDES.Des3Encrypt("TestString", "666666112222233333444446666665", "12345678"); // yJGf3qgWyoAQeaPY2S5Etg==
string jiamihou32 = SecurityDES.Des3Decrypt(jiamihou16, "666666112222233333444446666665", "12345678");
/// <summary>
/// 3DES 加密
/// </summary>
/// <param name="des3eninstr"></param>
/// <param name="des3key">24 位</param>
/// <param name="des3iv">8 位</param>
/// <returns></returns>
public static string Des3Encrypt(string des3eninstr, string des3key, string des3iv)
{
    string encryptPassword = string.Empty;
    SymmetricAlgorithm algorithm = new TripleDESCryptoServiceProvider();
    algorithm.Key = Encoding.UTF8.GetBytes(des3key);// Convert.FromBase64String(des3key);
    algorithm.IV = Encoding.UTF8.GetBytes(des3iv);
    algorithm.Mode = CipherMode.ECB;
    algorithm.Padding = PaddingMode.PKCS7;
    ICryptoTransform transform = algorithm.CreateEncryptor();
    byte[] data = Encoding.UTF8.GetBytes(des3eninstr);
    MemoryStream memoryStream = new MemoryStream();
    CryptoStream cryptoStream = new CryptoStream(memoryStream, transform, CryptoStreamMode.Write);
    cryptoStream.Write(data, 0, data.Length);
    cryptoStream.FlushFinalBlock();
    encryptPassword = Convert.ToBase64String(memoryStream.ToArray());
    memoryStream.Close();
    cryptoStream.Close();
    return encryptPassword;
}
/// <summary>
/// 3DES 解密
/// </summary>
/// <param name="des3deinstr">密文 Base64</param>
/// <param name="des3key">24 位</param>
/// <param name="des3iv">8 位</param>
/// <returns></returns>
public static string Des3Decrypt(string des3deinstr, string des3key, string des3iv)
{
    string decryptPassword = string.Empty;
    SymmetricAlgorithm algorithm = new TripleDESCryptoServiceProvider();
    algorithm.Key = Encoding.UTF8.GetBytes(des3key);
    algorithm.IV = Encoding.UTF8.GetBytes(des3iv);
    algorithm.Mode = CipherMode.ECB;
    algorithm.Padding = PaddingMode.PKCS7;
    ICryptoTransform transform = algorithm.CreateDecryptor(algorithm.Key, algorithm.IV);
    byte[] buffer = Convert.FromBase64String(des3deinstr);
    MemoryStream memoryStream = new MemoryStream(buffer);
    CryptoStream cryptoStream = new CryptoStream(memoryStream, transform, CryptoStreamMode.Read);
    StreamReader reader = new StreamReader(cryptoStream, System.Text.Encoding.ASCII);
    decryptPassword = reader.ReadToEnd();
    reader.Close();
    cryptoStream.Close();
    memoryStream.Close();
    return decryptPassword;
}

二、js 语言实现

以下是通过 crypto-js.js 实现。

1、DES

注意:mode 为空默认 CBC,此时偏移量 iv 不可为空。

注意:密钥可用位数为 8,如果超过 8 位以后的对加密结果无影响,且不会报错。

// 先引入 js 文件
<script src="http://cdn.bootcdn.net/ajax/libs/crypto-js/4.0.0/crypto-js.js"></script>
// npm(Node.js package manager)方式
> npm install crypto-js

// 调用方法 message() 查看测试结果
function message(){
    var outdata_value = encryptByDES("TestString", "66666611222");
    alert(outdata_value) // 57fe567eaa866373f851a526f07d9e26
    console.log("outdata_value-aes_encrypt:", outdata_value);
    outdata_value = decryptByDES(outdata_value, "66666611222");
    alert(outdata_value)
    console.log("outdata_value-aes_decrypt:", outdata_value);
}
//DES 加密
function encryptByDES(deseninstr, keystr, ivstr = keystr) {
    var keybyte = CryptoJS.enc.Utf8.parse(keystr);
    var ivbyte = CryptoJS.enc.Utf8.parse(ivstr);
    let afterEncrypt = CryptoJS.DES.encrypt(deseninstr, keybyte, {
        iv: ivbyte, // 当 mode 为 CBC 时,偏移量必传
        mode: CryptoJS.mode.ECB, // 为空默认 CBC
        padding: CryptoJS.pad.Pkcs7
    }).ciphertext.toString()
    console.log(afterEncrypt)
    return afterEncrypt
}
//DES 解密
function decryptByDES(desdeinstr, keystr, ivstr = keystr) {
    var keybyte = CryptoJS.enc.Utf8.parse(keystr);
    var ivbyte = CryptoJS.enc.Utf8.parse(ivstr);
    var decrypted = CryptoJS.DES.decrypt(
        { ciphertext: CryptoJS.enc.Hex.parse(desdeinstr) },
        keybyte,
        {
            iv: ivbyte, // 当 mode 为 CBC 时,偏移量必传
            mode: CryptoJS.mode.ECB, // 为空默认 CBC
            padding: CryptoJS.pad.Pkcs7
        }
    );
    console.log(decrypted);
    var result_value = decrypted.toString(CryptoJS.enc.Utf8);
    return result_value;
}

2、3DES

// 调用方法 message() 查看测试结果
function message() {
    var outdata_value = encryptByDES("TestString", "666666112222233333444446666665");
    alert(outdata_value) // yJGf3qgWyoAQeaPY2S5Etg==
        console.log("outdata_value-3des_encrypt:", outdata_value);
    outdata_value = decryptByDES(outdata_value, "666666112222233333444446666665");
    alert(outdata_value)
        console.log("outdata_value-3des_decrypt:", outdata_value);
}
// 加密 密钥需为 24 位,偏移量需为 8 位
function encryptByDES(deseninstr, keystr) {
    var keybyte = CryptoJS.enc.Utf8.parse(keystr);
    //var ivbyte = CryptoJS.enc.Utf8.parse(ivstr);
    var encrypted = CryptoJS.TripleDES.encrypt(deseninstr, keybyte, {
        // iv: ivbyte, // 当 mode 为 CBC 时,偏移量必传
        mode: CryptoJS.mode.ECB,
        padding: CryptoJS.pad.Pkcs7
        });
    return encrypted.toString();
}
// 解密 密钥需为 24 位,偏移量需为 8 位
function decryptByDES(desdeinstr, keystr) {
    var keybyte = CryptoJS.enc.Utf8.parse(keystr);
    //var ivbyte = CryptoJS.enc.Utf8.parse(ivstr);
    var decrypted = CryptoJS.TripleDES.decrypt(desdeinstr, keybyte, {
        // iv: ivbyte, // 当 mode 为 CBC 时,偏移量必传
        mode: CryptoJS.mode.ECB,
        padding: CryptoJS.pad.Pkcs7
        });
    return decrypted.toString(CryptoJS.enc.Utf8);
}

上文给大家详细介绍了在
Apinto 上实现
HTTP

gRPC
的协议转换

的基本内容,本篇我们将继续讲解如何在 Apinto-Dashboard 中进行配置。


配置 Apinto

Apinto 上我们提供了可视化界面工具
Apinto-Dashboard
,以降低初学者的使用成本,以下操作均在 Apinto-Dashboard 中进行配置。

1. 在全局插件中新建 http_to_grpc 插件

2. 创建 gRPC 服务

在这里,我们配置
gRPC
服务的相关信息,我们可以配置多个静态负载地址,这里我们填写了
127.0.0.1:9001

3.创建 http 路由,绑定 grpc_demo 上游服务

4. 在路由中绑定 http_to_grpc 插件

由于
gRPC
服务端示例中,我们开启了
gRPC
反射,因此,在配置插件时,开启
反射按钮
即可

注:

  • 当服务名称不填时,则默认使用
    HTTP
    请求路径的第一个
    /
    和第二个
    /
    之间的值作为服务名;

  • 当方法名称不填时,则默认使用
    HTTP
    请求路径的第二个 / 和第三个 / 之间的值作为服务名;
    ·即,若
    HTTP
    请求路径上
    /Service.Hello/Hello
    ,则此时服务名称为
    Service.Hello
    ,方法名称为
    Hello


关于 Protobuf 编码器


gRPC
未开启反射,我们需要先新建一个
Protobuf
编码器,绑定
http_to_grpc
插件时,绑定对应的编码器
ID
即可,详细步骤如下:

1. 创建 Protobuf 编码器

2. 在路由中绑定 http_to_grpc 插件

7.png

填写完后提交即可。


验证协议转换请求

1. 启动 gRPC 服务器

2.请求 Service.Hello 服务的 Hello 方法

在上文中,我们定义了 Hello 方法的功能:


  • HelloRequest
    中的
    name
    字段通过
    HelloResponse

    msg
    字段封装成
    hello,%s
    的结果返回;

  • 将请求的
    Header
    作为
    gRPC
    响应的 Trailer 头部返回。

调用结果如下:


欢迎到 GitHub 体验

来学点好玩的。


引入

我们也许学过,
\(FFT\)
可以解决一类卷积:

\[C_i=\sum^{k+j=i} A_iB_j
\]

现在我们稍微变一下式子:

\[C_i=\sum^{i=k \And j} A_kB_j
\]

\[C_i=\sum^{i =k\mid j} A_kB_j
\]

\[C_i=\sum^{i=k \oplus j} A_kB_j
\]

上面那个圆圆的东西是异或

怎么求?

\(FWT\)

也就是这个式子:

\[C_i=\sum^{i =k\mid j} A_kB_j
\]

\(FWT\)
的定义

模仿
\(FFT\)
,对于
\(A\)
我们想要在可接受时间内得到一个
\(FWT(A)\)
,使得

\[FWT(C)_i=FWT(A)_i\times FWT(B)_i
\]

\(i\)
代表第
\(i\)
个位置的数。

这样我们就可以
\(O(n)\)
暴力乘起来了。

因此我们构造
\(FWT(A)_i=\sum^{}_{j|i=i}A_j\)

现在我们来证明这个构造的正确性。

\[FWT(A)_i\times FWT(B)_i
\]

\[=\sum^{}_{j|i=i}A_j\times \sum^{}_{k|i=i}B_k
\]

\[=\sum^{}_{j|i=i}\sum^{}_{k|i=i}A_j B_k
\]

因为可以从
\(j|i=i\)

\(k|i=i\)
中得出
\((j|k)|i=i\)
,所以我们还可以消去另一个式子

\[=\sum^{}_{(j|k)|i=i}A_j B_k
\]

根据
\(FWT\)
的定义,这个式子就是
\(FWT(C)_i\)
。证毕。

另一种理解

涉及到了或运算,我们不妨把数全都变成二进制。于是我们想到一种经典转换:将二进制中的
\(0\)

\(1\)
转化为集合中一个数选还是不选。那么或操作代表什么呢?

bingo!两个集合的并集!

于是我们可以把上面的式子改写一个形式:

\[C_i=\sum^{i=k \mid j} A_kB_j
\]

变成

\[C_i=\sum^{i =k\bigcup j} A_kB_j
\]

注意看,这时
\(i,j,k\)
都是集合,只不过我们将其用二进制表示.

这样我们可以改写
\(FWT\)
的定义。

重新来一遍,
\(FWT(A)_i=\sum^{}_{k \subseteq i} A_k\)

因此我们为
\(FWT\)
找到了新的定义,他代表着集合
\(i\)
的子集之和。我们有了更自然的推导:

\[\sum^{}_{j \subseteq i}A_j\times \sum^{}_{k \subseteq i}B_k
\]

\[=\sum^{}_{j,k \subseteq i}A_j\times B_k
\]

\[=\sum^{}_{x \subseteq i}\sum^{}_{j\bigcup k = x }A_j\times B_k
\]

\[=\sum^{}_{x \subseteq i}C_x
\]

\[=FWT(c)_x
\]

换句话说,我们对子集做了个前缀和操作(发现了吗?子集的前缀和进行或卷积与普通前缀和进行加法卷积具有相似性),并用前缀和相乘代替了原来的
\(O(n^2)\)
相乘。

如何变化

我们把原序列
\(A\)
按下标最高位是
\(0\)
还是
\(1\)
分成两部分
\(A_0\)

\(A_1\)
分治求解。显然,前半部分(最高位为
\(0\)
的部分)就是
\(FWT(A_0)\)
,所以我们考虑后半部分的答案。

后半部分最高位为
\(1\)
,因此此时“子集”这一概念不仅包含分治处理的他子集,还包括把最大值变为
\(0\)
后的,序列
\(A0\)
中同一位置的子集。要将
\(A_0\)
中的同一位置加到当前答案上。

写成数学形式就是:

\[FWT(A) = merge(FWT(A_0),FWT(A_0)+FWT(A_1))
\]

上面的
\(merge\)
代表拼接,就是字面意思。

于是我们就能写出分治递归代码了!但为了常数着想,我们试着把递归这一步骤去掉。

去掉的部分并不难写,我们按照层数从小到大递归,不难发现第
\(i\)
层(从
\(0\)
开始编号,最底层为
\(0\)
)就是枚举第
\(i\)
位是
\(0\)
还是
\(1\)
,并且乱填其他数进行转移。

代码也简单:

void OR(mint *f){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)// k 为当前的层,o 仅用于穷举左边进行转移
        for(int i = 0; i < n; i += o)// 穷举左边
            for(int j = 0; j < k; j++){ // 穷举右边
                f[i + j + k] = f[i + j + k] + f[i + j];
            }
}

如何转回来

再看一眼转移的式子

\[FWT(A) = merge(FWT(A_0),FWT(A_0)+FWT(A_1))
\]

思考只有两个数的情况。此时
\(1\)
位置是不会变的,
\(2\)
位置加上了
\(1\)
位置的贡献,要减去。

我们发现更大的情况也是一样的,只要依次把前面的贡献减去就好。

void IOR(mint *f){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)// k 为当前的层,o 仅用于穷举左边进行转移
        for(int i = 0; i < n; i += o)// 穷举左边
            for(int j = 0; j < k; j++){ // 穷举右边
                f[i + j + k] = f[i + j + k] - f[i + j];
            }
}

这两份代码显然是可以合并的。因此我们得到了
\(FWT\)
或 的全过程。

void OR(mint *f, int type){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++){
                f[i + j + k] = f[i + j + k] + (f[i + j] * mint(type));
            }
}

\(FWT\)

和 或 差不多,只是要从
\(1\)
转移到
\(0\)

可以发现,实际上我们用子集后缀和优化了运算。

void AND(mint *f, int type){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++)
                f[i + j] = f[i + j] + (f[i + j + k] * mint(type));
}

\(FWT\)
异或

\[C_i=\sum^{i=k \oplus j} A_kB_j
\]

很遗憾,我并没有发现这个东西的集合意义,如果有大佬知道可以告诉我。。。

正着转化

思考
\(FWT\)
的作用,我们想要把
\(A_kB_j\)
变成
\(A_iB_i\)
的形式,以此来简化运算。

我们考虑这样
\(n\)

\(n\)
维向量
\(b\)

\(b(i)\)
只有下标
\(i\)
处是
\(1\)
,其他位置都是
\(0\)

现在我们把
\(FWT\)
后的
\(A,B\)
看作系数,此时显然
\(A_1b(1),A_2b(2),...,A_nb(n)=A_1,A_2,A_3,A_4...,A_n\)

显然,异或卷积对于乘法有分配律。

设异或卷积为
\(\ast\)
,则

\[(\sum^{n}_{i=1} A_ib(i)) \ast (\sum^{n}_{i=1} B_jb(j))
\]

\[=(\sum^{n}_{i=1}\sum^{n}_{j=1} A_iB_j (b(i)\ast b(j))
\]

发现后面的东西可以简单表示,即
\(b_i \ast b_i = b_i,b_i \ast b_j = 0(i \neq j)\)

那么整个式子就是我们寻找的形式:

\[\sum^{n}_{i=1} A_iB_i
\]

而我们要做的事情无非是求出
\(FWT\)
之前的
\(b_i\)

太长不看版:异或
\(FWT\)
与原序列线性相关

既然这样,我们设
\(FWT(A)_x=\sum^{n}_{i=1} g(x,i)A_i\)

那么因为
\(FWT(C)_x=FWT(A)_x\times FWT(b)_x\)

所以
\(\sum^{n}_{k=1} g(x,k)C_k=\sum^{n}_{i=1} g(x,i)A_i \times \sum^{n}_{j=1} g(x,j)B_j\)

整理一下可以得出:

\[\sum^{n}_{k=1} g(x,k)C_k=\sum^{n}_{i=1}\sum^{n}_{j=1} g(x,i)g(x,j)\times A_iB_j
\]


\(C_k\)

\(A,B\)
表示可得:

\[\sum^{n}_{k=1} g(x,k)\sum^{k=i \oplus j} A_iB_j=\sum^{n}_{i=1}\sum^{n}_{j=1} g(x,i)g(x,j)\times A_iB_j
\]

更改求和顺序,我们枚举
\(i,j\)
可得:

\[\sum^{n}_{i=1}\sum^{n}_{j=1} g(x,i \oplus j) A_iB_j=\sum^{n}_{i=1}\sum^{n}_{j=1} g(x,i)g(x,j)\times A_iB_j
\]

于是我们发现了
\(g\)
的关系:

\[g(x,i \oplus j) = g(x,i)g(x,j)
\]

现在问题来了,与
\(i,j\)
相关的什么东西,使异或之后的值等于原来两值的乘积?

于是我们可以想到
有人托梦给我
奇偶性。

具体的,我们发现异或前后
\(1\)
的个数奇偶性不变。原因如下:

按每一位依次考虑。如果第
\(i\)
位异或后为
\(1\)
,那么原来必定有且仅有一个
\(1\)
。个数不变

如果为
\(0\)
,要么是两个
\(0\)
,此时
\(1\)
的个数不变,要么是两个
\(1\)
,此时
\(1\)
的个数减
\(2\)
,奇偶性仍不变。

所以我们定义
\(g(x,i)=(-1)^{|i \bigcap x|}\)
。那么上式就等价于:

\[(-1)^{|(i \oplus j) \bigcap x|} = (-1)^{|i \bigcap x|}(-1)^{|j \bigcap x|}
\]

根据上面的推论,左右两边奇偶性不变,与 后无非是减去两个相同的数,奇偶性还是不变。

于是我们得出
\(FWT\)
的转移式:

\[FWT(A)_x=\sum^{n}_{i=1} (-1)^{|i \bigcap x|}A_i
\]

如何求解

考虑模仿前两个
\(FWT\)
的形式,讨论最高位
\(i\)

\(0\)
和为
\(1\)
两种情况。

原来最高位为
\(0\)

\(FWT\)
后的前
\(2^{i-1}\)
个数最高位还是
\(0\)
。由于
\(1 \And 0=0\)
,所以后
\(2^{i-1}\)
个数的贡献为正。前半部分答案为
\(FWT(A_0)+FWT(A_1)\)

\(FWT\)
后的后
\(2^{i-1}\)
个数最高位变成了
\(1\)
,此时
\(A_0\)
的贡献还是正(因为
\(1 \And 0=0\)
)。但是此时后半部分加了
\(1\)
,于是贡献要取反。后半部分答案为
\(FWT(A_0)-FWT(A_1)\)

所以我们得出:

\[FWT(A) = merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))
\]

当然,参照 或 FWT,我们可以写出不依赖递归的程序:

void XOR(mint *f){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)//具体意义参考 FWT 或
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j ++){
                mint x = f[i + j], y = f[i + j + k];
                f[i + j] = x + y;
                f[i + j + k] = x - y;
            }
}

求逆变换

实际上就是把贡献减去

\[IFWT(A) = merge(\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1))}{2}
\]

显然这两个东西是可以合并的。于是我们可以得出
模板
的完整代码:

#include<bits/stdc++.h>
using namespace std;

#define forp(i, a, b) for(int i = (a);i <= (b);i ++)
#define forc(i, a, b) for(int i = (a);i >= (b);i --)

const int maxn = 6e5 + 5;
const int mod = 998244353;

int read(){
    int u;cin >> u;return u;
}

class mint{
    private : int v;
    public:
        mint(){}
        int operator()(void)const{
            return v;
        }
        mint (const int &u){ 
            v = u % mod; 
        }
        mint operator+(const mint &a) const{ 
            int x = a.v + v;
            if(x >= mod) return mint(x - mod);
            if(x < 0) return mint(x + mod);
            return x;
        }
        mint operator-(const mint& a)const{
			return v < a.v ? v - a.v + mod : v - a.v;
		}
        mint operator*(const mint &a) const{
            return mint((1ll * a.v * v) % mod);
        }
};

mint qpow(mint u, int v){
    mint ans = mint(1);
    while(v){
        if(v & 1) ans = ans * u;
        u = u * u;
        v >>= 1;
    }
    return ans;
}
mint inv2 = qpow(2, mod - 2);

int n;
mint A[maxn], B[maxn], C[maxn];
mint g[maxn];

void OR(mint *f, int type){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++){
                f[i + j + k] = f[i + j + k] + (f[i + j] * mint(type));
            }
}

void AND(mint *f, int type){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j++)
                f[i + j] = f[i + j] + (f[i + j + k] * mint(type));
}

void XOR(mint *f, int type){
    for(int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
        for(int i = 0; i < n; i += o)
            for(int j = 0; j < k; j ++){
                mint x = f[i + j], y = f[i + j + k];
                f[i + j] = x + y;
                f[i + j + k] = x - y;
                if(type == -1){
                    f[i + j] = f[i + j] * inv2;
                    f[i + j + k] = f[i + j + k] * inv2;
                }
            }
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

    n = (1 << read());
    forp(i, 0, n - 1) A[i] = mint(read());
    forp(i, 0, n - 1) B[i] = mint(read());

    OR(A, 1);OR(B, 1);
    forp(i, 0, n - 1) C[i] = (A[i] * B[i]);
    OR(C, -1);
    forp(i, 0, n - 1) cout << C[i]() << ' ';
    cout << endl;
    OR(A, -1);OR(B, -1);

    AND(A, 1);AND(B, 1);
    forp(i, 0, n - 1) C[i] = (A[i] * B[i]);
    AND(C, -1);
    forp(i, 0, n - 1) cout << C[i]() << ' ';
    cout << endl;
    AND(A, -1);AND(B, -1);

    XOR(A, 1);XOR(B, 1);
    forp(i, 0, n - 1) C[i] = (A[i] * B[i]);
    XOR(C, -1);
    forp(i, 0, n - 1) cout << C[i]() << ' ';
    cout << endl;
    XOR(A, -1);XOR(B, -1);
    return 0;
}

大概就是这样。。。应用也许会另外开坑吧。


后记

感谢
xht 的博客
,从这篇博客里我学到了 FWT 的基础知识。

感谢同校大佬
yllcm
为本人解释符号与定义。

感谢万能的U群群友 Untitled_unrevised 解释 FWT 的目的。

感谢万能的U群群友 rqy 学姐与 樱初音斗橡皮 解释为什么异或 FWT 是线性变换
顺便发现了我在线性代数方面的巨大缺口

“文心”取自《文心雕龙》一书的开篇,作者刘勰在书中引述了一个古代典故:春秋时期,鲁国有一位名叫孔文子的大夫,他在学问上非常有造诣,但是他的儿子却不学无术,孔文子非常痛心。

一天,孔文子在山上遇到了一位神仙,神仙告诉他:“你的儿子之所以不学无术,是因为你没有给他灌输文心,让他懂得文学的魅力和意义。”孔文子听后深受启发,回家后开始给儿子灌输文学知识,儿子也逐渐对学问产生了兴趣,最终成为了一位有学问的人。因此,刘勰在书中将“文心”解释为“灌输文学知识的心灵”之意。

百度以“文心”命名自己的AI产品线,可见其对自己的中文处理能力是极为自信的,ERNIE3.0对标
ChatGPT3.5/4.0
,ERNIE-ViLG对标
Stable-Diffusion
,文心PLATO则可以理解为ChatGPT的embedding,可谓是野心勃勃。

文心一言SDK引入

百度目前已经开源文心一言的sdk工具包:

pip3 install --upgrade wenxin-api

和百度云产品线一样,安装好以后,需要去文心一言官网获取appkey和appsecret

随后编写请求逻辑:

import wenxin_api   
from wenxin_api.tasks.free_qa import FreeQA  
wenxin_api.ak = "your ak" #输入您的API Key  
wenxin_api.sk = "your sk" #输入您的Secret Key  
input_dict = {  
    "text": "问题:天为什么这么蓝?\n回答:",  
    "seq_len": 512,  
    "topp": 0.5,  
    "penalty_score": 1.2,  
    "min_dec_len": 2,  
    "min_dec_penalty_text": "。?:![<S>]",  
    "is_unidirectional": 0,  
    "task_prompt": "qa",  
    "mask_type": "paragraph"  
}  
rst = FreeQA.create(**input_dict)  
print(rst)

程序返回:

{  
  "code": 0,  
  "msg": "success",  
  "data": {  
    "result": "因为我们有个好心情",  
    "createTime": "2023-03-16 16:02:10",  
    "requestId": "71a6efb46acbd64394374f44579a01eb",  
    "text": "天为什么这么蓝",  
    "taskId": 1000000,  
    "status": 1 # 0表示生成中,1表示生成成功  
  }  
}

请求的参数含义请参照官方文档:

async  
异步标识	int	1	  
1  
是  
异步标识,现阶段必传且传1  
text  
用户输入文本	string	空	  
[1, 1000]  
是  
模型的输入文本,为prompt形式的输入。  
min_dec_len  
最小生成长度	int	1	  
[1,seq_len]  
是  
输出结果的最小长度,避免因模型生成END导致生成长度过短的情况,与seq_len结合使用来设置生成文本的长度范围。  
seq_len  
最大生成长度	int	128	  
[1, 1000]  
是  
输出结果的最大长度,因模型生成END或者遇到用户指定的stop_token,实际返回结果可能会小于这个长度,与min_dec_len结合使用来控制生成文本的长度范围。  
topp  
多样性	float	1.0	  
[0.0,1.0],间隔0.1  
是  
影响输出文本的多样性,取值越大,生成文本的多样性越强。  
penalty_score  
重复惩罚	float	1.0	  
[1,2]  
否  
通过对已生成的token增加惩罚,减少重复生成的现象。值越大表示惩罚越大。设置过大会导致长文本生成效果变差。  
stop_token  
提前结束符	string	空		  
否  
预测结果解析时使用的结束字符串,碰到对应字符串则直接截断并返回。可以通过设置该值,可以过滤掉few-shot等场景下模型重复的cases。  
task_prompt  
任务类型	string	空	PARAGRAPH,   
SENT, ENTITY,   
Summarization, MT,   
Text2Annotation,  
Misc, Correction,   
QA_MRC, Dialogue,   
QA_Closed_book,   
QA_Multi_Choice,  
QuestionGeneration,   
Paraphrasing, NLI,   
SemanticMatching,   
Text2SQL,   
TextClassification,   
SentimentClassification,  
zuowen, adtext,   
couplet,novel,  
cloze	  
否  
指定预置的任务模板,效果更好。 PARAGRAPH:引导模型生成一段文章; SENT:引导模型生成一句话; ENTITY:引导模型生成词组; Summarization:摘要; MT:翻译; Text2Annotation:抽取; Correction:纠错; QA_MRC:阅读理解; Dialogue:对话; QA_Closed_book: 闭卷问答; QA_Multi_Choice:多选问答; QuestionGeneration:问题生成; Paraphrasing:复述; NLI:文本蕴含识别; SemanticMatching:匹配; Text2SQL:文本描述转SQL;TextClassification:文本分类; SentimentClassification:情感分析; zuowen:写作文; adtext:写文案; couplet:对对联; novel:写小说; cloze:文本补全; Misc:其它任务。  
typeId  
模型类型	int	1	1	  
是  
通用:  
1 ERNIE 3.0 Zeus 通用  
2 ERNIE 3.0 Zeus instruct模型  
同义改写  
1 ERNIE 3.0 Zeus 同义改写精调模型  
写作文:  
1 ERNIE 3.0 Zeus 记叙文增强包  
2 ERNIE 3.0 Zeus 议论文增强包  
3 ERNIE 3.0 Zeus 小学作文增强包  
写文案:  
1 ERNIE 3.0 百亿 社交短文案精调模型  
2 ERNIE 3.0 Zeus 商品营销文案增强包  
写摘要:  
1 ERNIE 3.0 Zeus 写摘要  
2 ERNIE 3.0 Zeus 写标题  
3 ERNIE 3.0 百亿 写标题  
对对联:  
1 ERNIE 3.0 Zeus 对对联  
2 ERNIE 3.0 百亿 对对联  
自由问答:  
1 ERNIE 3.0 Zeus 自由问答增强包  
2 ERNIE 3.0 百亿 自由问答  
3 ERNIE 3.0 Zeus instruct模型  
写小说  
1 ERNIE 3.0百亿 写小说精调模型  
补全文本  
1 ERNIE 3.0 Zeus 词补全增强包  
2 ERNIE 3.0 Zeus 句补全增强包  
3 ERNIE 3.0 Zeus 段落补全增强包  
penalty_text  
惩罚文本	string	空		  
否  
模型会惩罚该字符串中的token。通过设置该值,可以减少某些冗余与异常字符的生成。  
choice_text  
候选文本	string	空		  
否  
模型只能生成该字符串中的token的组合。通过设置该值,可以对某些抽取式任务进行定向调优。  
is_unidirectional  
单双向控制开关	int	0	  
0或1  
否  
0表示模型为双向生成,1表示模型为单向生成。建议续写与few-shot等通用场景建议采用单向生成方式,而完型填空等任务相关场景建议采用双向生成方式。  
min_dec_penalty_text  
最小惩罚样本	string	空		  
否  
与最小生成长度搭配使用,可以在min_dec_len步前不让模型生成该字符串中的tokens。  
logits_bias  
屏蔽惩罚	float	-10000	  
[1, 1000]  
否  
配合penalty_text使用,对给定的penalty_text中的token增加一个logits_bias,可以通过设置该值屏蔽某些token生成的概率。  
mask_type  
生成粒度	string	word	  
可选参数为word, sentence, paragraph  
否  
设置该值可以控制模型生成粒度。

这里需要注意的是,虽然参数支持async异步,但那不是指请求的异步方式返回,换句话说,文心模型返回还是需要等待的,并不是ChatGPT那种流式返回模式。

文心一言API调用

文心一言SDK的功能有限,也不支持异步请求调用,如果需要定制化或者使用别的语言请求文心一言,需要提前发起Http请求获取token,这里我们使用异步请求库httpx:

pip3 install httpx

添加获取token逻辑:

class Winxin:  
  
    def chat(self,text):  
        input_dict = {  
            "text": f"问题:{text}\n回答:",  
            "seq_len": 512,  
            "topp": 0.5,  
            "penalty_score": 1.2,  
            "min_dec_len": 2,  
            "min_dec_penalty_text": "。?:![<S>]",  
            "is_unidirectional": 0,  
            "task_prompt": "qa",  
            "mask_type": "paragraph"  
        }  
        rst = FreeQA.create(**input_dict)  
        print(rst)  
  
    async def get_token(self):  
  
        headers = {"Content-Type":"application/x-www-form-urlencoded"}  
  
        async with httpx.AsyncClient() as client:  
            resp = await client.post(f"https://wenxin.baidu.com/moduleApi/portal/api/oauth/token?grant_type=client_credentials&client_id={wenxin_api.ak}&client_secret={wenxin_api.sk}",headers=headers)  
            result = resp.json()  
            print(result)

异步调用文心一言接口的token:

if __name__ == '__main__':  
      
    wx = Winxin()  
    asyncio.run(wx.get_token())

程序返回:

{'code': 0, 'msg': 'success', 'data': '24.3f6a63545345ae6588ea86a353.86400000.1679123673218.92a99f8955c6f9ab2c438a5f31b5d73b-173001'}

这里返回的数据的data就是token,有效期是一天,吐槽一下,居然没有refreshtoken,也就是说过期了还得重新去请求,不能做到无感知换取。

随后请求接口换取taskid:

  

async def get_task(self,token,text):  
  
        url = "https://wenxin.baidu.com/moduleApi/portal/api/rest/1.0/ernie/3.0.25/zeus"   
          
        data = {"async": 1, "typeId": 1, "seq_len": 512, "min_dec_len": 2, "topp": 0.8, "task_prompt": "qa", "penalty_score": 1.2, "is_unidirectional": 0, "min_dec_penalty_text": "。?:![<S>]", "mask_type": "word","text":text}  
  
        headers = { "Content-Type": "application/x-www-form-urlencoded" }  
  
        params = { "access_token": token }  
  
        async with httpx.AsyncClient() as client:  
  
            result = client.post(url, headers=headers, params=params, data=data)  
  
            result = result.json()  
  
            print(result)


返回:

{  
    "code":0,  
    "msg":"success",  
    "data":{  
        "taskId": 1229202,  
        "requestId":"7fad28872989e274914ee1687b8f2a13"  
    }  
}

最后请求结果:

async def get_res(self,taskid,token):  
  
        url = "https://wenxin.baidu.com/moduleApi/portal/api/rest/1.0/ernie/v1/getResult"   
  
        access_token = token  
          
        task_id = taskid  
  
        headers = { "Content-Type": "application/x-www-form-urlencoded" }  
  
        params = { "access_token": access_token }  
  
        data = { "taskId": task_id }  
  
        async with httpx.AsyncClient() as client:  
  
            response = client.post(url, headers=headers, params=params, data=data)  
  
            print(response.text)

结果和SDK请求方式一致:

{  
  "code": 0,  
  "msg": "success",  
  "data": {  
    "result": "因为我们有个好心情",  
    "createTime": "2023-03-16 18:09:40",  
    "requestId": "71a6efb46acbd64394374f44579a01eb",  
    "text": "天为什么这么蓝",  
    "taskId": 1000000,  
    "status": 1 # 0表示生成中,1表示生成成功  
  }  
}

文心一格文字生成图像

ERNIE-ViLG AI作画大模型:文心ERNIE-ViLG2.0 是基于用户输入文本、或文本加图片生成图像及图像编辑功能的技术,主要为用户提供跨模态的文本生成图像的大模型技术服务。

文心一格和文心一言是共享appkey和appsecret的,添加图像生成逻辑:



class Winxin:  
  
    def draw(self,text):  
  
        num = 1  
        input_dict = {  
            "text": "国画,工笔画,女侠,正脸",  
            "style": "工笔画",  
            "resolution":"1024*1024",  
            "num": num  
        }  
        rst = TextToImage.create(**input_dict)  
        print(rst)


程序返回:

{  
    "imgUrls":[  
        "https://wenxin.baidu.com/younger/file/ERNIE-ViLG/61157afdaef4f0dfef0d5e51459160fbex"  
    ]  
}

效果:

对比基于Stable-Diffusion算法的Lora模型:

大家丰俭由己,各取所需。

需要注意的是,该产品线并不是免费的:

免费送200张,想继续玩就得充值,不愧是百度。话说免费的Stable-Diffusion不香吗?

结语

产品力而言,ChatGPT珠玉在前,文心一言还有很长的路需要走,用三国时期徐庶自比孔明的话来讲:“驽马焉敢并麒麟,寒鸦岂能配凤凰”。但是,也没必要一片挞伐之声,俄国著名作家契诃夫曾经说,“大狗叫,小狗也要叫”,ChatGPT虽然一座遥不可及的高峰,但是其他公司也无须放弃人工智能领域的研究,毕竟作为最老牌的中文搜索引擎,百度浸润几十年的中文处理能力,还是无人能出其右的。

新建的 Word 文档,默认纸张为 A4 纸,大小为 21 厘米 × 29.7 厘米,没特殊要求的文档用 A4 纸即可,但有时文档中的内容比较宽,需要用比 A4 纸更宽的纸张,例如制作一些宽的表格,就需要选择宽的纸张;另外,如果要制作一些法律类、信封类、信纸类等的文档,需要选择相应的纸张。那么如何更改Word中的页面大小和页面方向呢?今天我就将为大家介绍一种高效便捷的方法,通过Java应用程序,以编程方式更改Word中的页面大小和页面方向。下面是我整理的具体步骤及方法,并附上Java代码供大家参考。一起来学习吧!

程序环境:

方法1:
手动引入。将
Free Spire.Doc for Java
下载到本地,解压,找到lib文件夹下的Spire.Doc.jar文件。在IDEA中打开如下界面,将本地路径中的jar文件引入Java程序

方法2: 如果您想通过
Maven
安装,则可以在 pom.xml 文件中添加以下代码导入 JAR 文件。

<repositories>

        <repository>

            <id>com.e-iceblue</id>

            <url>https://repo.e-iceblue.cn/repository/maven-public/</url>

        </repository>

    </repositories>

<dependencies>

    <dependency>

        <groupId>e-iceblue</groupId>

        <artifactId>spire.doc.free</artifactId>

        <version>5.2.0</version>

    </dependency>

</dependencies>

更改Word中的页面大小和页面方向

以下是在 Word 文档中设置装订页边距的步骤:

  • 创建一个Document实例。
  • 使用 Document.loadFromFile() 方法加载 Word 文档。
  • 使用 Document.getSections().get() 方法获取特定节。
  • 使用 Section.getPageSetup().setGutter() 方法为该指定节设置装订页边距。
  • 使用 Document.saveToFile() 方法将文档保存到文件。

完整代码

Java

import com.spire.doc.*;import com.spire.doc.documents.*;public classWordPageSetup {public static void main(String[] args) throwsException {//创建一个Document实例
        Document doc= newDocument();//加载 Word 文档
        doc.loadFromFile("我与地坛.docx");//获取特定节
        Section section = doc.getSections().get(0);//将页面大小更改为 A3
section.getPageSetup().setPageSize(PageSize.A3);//将页面方向更改为横向
section.getPageSetup().setOrientation(PageOrientation.Landscape);//将文档保存到文件
        doc.saveToFile("结果文档.docx",FileFormat.Docx_2013);
}
}

效果图

以上就是更改Word中的页面大小和页面方向的方法介绍,操作很简单的,大家学会了吗?希望能对大家有所帮助!