关于T4

关于T4的一些奥妙重重的题解。

实际上题解还算人话（，但是有些细节的地方有些吊诡。而且鉴于大家大概没学过任何生成函数理论那来普及一波。还可以水博客。

首先解释一下开头那个诡异的式子。

我们看见这个题一般都是先打个表。

（joke3579跟我说这玩意有用吗，我的评价是管有没有用先打上）

实际上这玩意确实没有用，但是很优美（

然后回顾一下我们关于逆序对个数的 \(dp\) 式子：设 \(dp[i][j]\) 为 \(i\) 长度的排列，有 \(j\) 个逆序对的方案数，我们每次插入数 \(i\) ，可以得到：

然后我们看第 \(i\) 行每个数对于下一行位置的贡献。发现： 第 \(0\) 列可以加到下一行的 \(0,1,\dots,i\) 上，第 \(1\) 列可以加到下一行的 \(1,2,\dots,i+1\) 上，以此类推。这启示我们使用形式幂级数解决问题。

我们设第 \(n\) 行的答案的生成函数为 \(F_n(x)\) 。如果您不知道这是个什么东西的话可以理解成这是个无穷级数，第 \(x^i\) 项的系数就是上面那个表第 \(n\) 行第 \(i\) 列的答案。

那么如果我们把它乘一个 \(x\) 那所有的系数就相当于向右挪了一位。因此上面的就相当于加上挪 \(0\) 位，挪 \(1\) 位，挪 \(2\) 位，一直到 \(n-1\) 位。也就是

后面那一步就是个等比数列求和。

然后我们发现第 \(1\) 行只有 \(0\) 列是个 \(1\) ，那不就是 \(1\) 吗。所以我们有第 \(n\) 行的答案就是：

然后我们把它拆开成上下两部分。上面的部分：

我们有一个奥妙重重的结论：

具体的bdfs“五边形数定理”。证明不重要，欧拉也拖了十年才发结论。然后观察到后面指数是个 \(i\times i\) 的东西所以它只有 \(O(\sqrt n)\) 项，暴力求就行。

然后是下面的东西：

广义二项式定理：

使用上指标反转：（如果您不知道的话翻具体数学或者看我曾经的某些东西）

然后我们是 \(\mod 2\) 意义下计算的，所以只需要 \(\binom{k+n-1}{n-1}\mod 2\) 的值。

上Lucas定理，发现 \(\mod 2\) 就相当于把上下指标都拆成二进制位算组合数乘起来。然后要求所有的结果都是 \(1\) ，那么就是所有 \(n-1\) 在二进制位有值的地方 \(k+n-1\) 也必须有值，就是

后面转换显然，读者自证不难。

那么这个东西其实就是 \(\prod_{2^t\&(n-1)=0}1+x^{2^t}\) 。

所以我们直接扫 \(n-1\) 的每个二进制位，开个bitset算就行了。乘一个 \(x^{2^t}\) 相当于异或上左移之后的值。复杂度 \(O(\frac{n\log n}{\omega})\) 。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
int n,m;
bitset<100000001>a;
int main(){
    scanf("%d%d",&n,&m);
    a[0]=1;
    for(int i=1;;i++){
        if(i*(3*i+1)/2<=n)a[i*(3*i+1)/2]=1;
        if(i*(3*i-1)/2<=n)a[i*(3*i-1)/2]=1;
        else break;
    }
    for(int i=0;i<=__lg(n);i++){
        if(((1<<i)&(n-1))==0)a^=(a<<(1<<i));
    }
    while(m--){
        int x;scanf("%d",&x);
        a[x]?putchar('1'):putchar('0');
    }
    return 0;
}

好您现在看完了。请问我以后还需不需要把每一步都解释一遍？请留下评论。

原文地址：http://www.cnblogs.com/gtm1514/p/16794314.html