2020牛客暑期多校训练营（第六场）B

题目描述

Roundgod is obsessive about linear algebra. Let $\mathrm A=\{0,1\}$ , everyday she will generate a binary vector randomly in $\mathrm A^n$ . Now she wonders the probability of generating $n$ linearly independent vectors in the next $n$ days modulo $10^9+7$ . Formally, it can be proved that the answer has the form of $\frac{P}{Q}$ , where $P$ and $Q$ are coprime and $Q$ is not a multiple of $10^9+7$ . The answer modulo $10^9+7$ thus means $P \cdot Q^{-1}\pmod{10^9+7}$ , where $Q^{-1}$ is the multiplicative inverse of $10^9+7$ .
Wcy thinks the problem too easy. Let the answer of $n$ be $f_n$ , she wants to know $f_1\oplus f_2\oplus ...\oplus f_n$ , where $\oplus$ denotes bitwise exclusive or operation.
Note that when adding up two vectors, the components are modulo $2$ .

输入描述

The input contains multiple test cases. The first line of input contains one integer $T$ $(1\leqslant T\leqslant 1000 )$ , denoting the number of test cases.
In the following $T$ lines, each line contains an integer $n$ $(1\leqslant n\leqslant 2\times 10^7 )$ describing one test case.

输出描述

For each test case, output one integer indicating the answer.

示例1

输入

输出

500000004
194473671
861464136

说明

$f(1)=\frac{1}{2}\\ f(2)=\frac{3}{8}\\ f(3)=\frac{21}{64}$

分析

首先说明，向量各个维度的坐标都是在模 $2$ 意义下的，基于此可以有如下性质。对于两个向量 $\vec a$ 和 $\vec b$ ， $\vec a+\vec b=\vec a-\vec b=\vec b-\vec a$ ，这三者可视为同一向量。对于一个向量 $\vec x$ ， $\forall\ k\in\mathbb N$ ，若 $k$ 为偶数，那么 $k\vec x=\vec 0$ ；若 $k$ 为奇数，那么 $k\vec x=\vec x$ 。基于以上，两个向量 $\vec a$ 和 $\vec b$ 的线性组合只有 $\vec a,\vec b,\vec a+b,\vec 0$ 这四个向量。
$f_n$ 表示随机生成 $n$ 个线性无关的 $n$ 维向量的概率。由于要使 $n$ 个 $n$ 维向量组成的向量组线性无关，因此考虑添加第 $i$ 个 $n$ 维向量 $\vec x$ 时， $\vec x$ 必须不属于前 $i-1$ 个线性无关的向量构成的向量空间。接下来尝试枚举 $i$ 来寻找规律。
当 $i=2$ ，已有的线性无关向量组为 $\vec a$ ；同 $\vec a$ 组成线性相关向量组的向量有 $\vec 0,\vec a$ 。当 $i=3$ ，已有的线性无关向量组为 $\vec a,\vec b$ ，那么同 $\vec a,\vec b$ 构成线性相关向量组的向量有 $\vec 0,\vec a,\vec b,\vec a+\vec b$ 。当 $i=4$ ，已有的线性无关向量组为 $\vec a,\vec b,\vec c$ ，那么同 $\vec a,\vec b,\vec c$ 构成线性相关向量组的向量有 $\vec 0,\vec a,\vec b,\vec c,\vec a+\vec b,\vec a+\vec c,\vec b+\vec c,\vec a+\vec b+\vec c$ 。基于以上，假设已经存在 $i-1$ 个线性无关的向量 $\vec{\alpha_1},\vec{\alpha_2},\cdots,\vec{\alpha_{i-1}}$ ，如果再添加一个向量 $\vec x$ ，使得 $\vec{\alpha_1},\vec{\alpha_2},\cdots,\vec{\alpha_{i-1}},\vec x$ 线性相关，那么 $\vec x$ 的取值有 $\sum\limits_{j=0}^{i-1}\binom{i-1}{j}=2^{i-1}$ 种；该式意味着每次在 $i-1$ 个向量中取 $j$ 个向量 $\vec{\alpha_{i_1}},\vec{\alpha_{i_2}},\cdots,\vec{\alpha_{i_j}}$ ，令 $\vec x=\vec{\alpha_{i_1}}+\vec{\alpha_{i_2}}+\cdots+\vec{\alpha_{i_j}}$ 。
第 $i$ 个向量是 $n$ 维向量，必然有 $2^n$ 种可能；但是由于已经存在 $i-1$ 个线性无关的向量，因此其中 $2^{i-1}$ 种取值必然会与前 $i-1$ 个向量组成线性相关的向量组，只有 $2^n-2^{i-1}$ 种取值是合法的。因此，第 $i$ 个向量与前 $i-1$ 个线性无关的向量组成线性无关组的概率为 $\frac{2^n-2^{i-1}}{2^n}$ 。故当 $n\geqslant 2$ 时， $n$ 个 $n$ 维向量组成线性无关组的概率 $f_n=\frac{1}{2}\prod\limits_{i=2}^n\frac{2^n-2^{i-1}}{2^n}=\prod\limits_{i=1}^n\frac{2^n-2^{i-1}}{2^n}$ ；显然，当 $n=1$ 时符合上式，故 $f_n=\prod\limits_{i=1}^n\frac{2^n-2^{i-1}}{2^n}$ 。
可见， $f_n=\frac{(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})}{2^{n^2}}$ ，而 $f_{n-1}=\frac{(2^{n-1}-1)(2^{n-1}-2)\cdots(2^{n-1}-2^{n-2})}{2^{(n-1)^2}}$ 。因此有 $2^{n-1}f_{n-1}=\frac{(2^n-2)\cdots(2^n-2^{n-1})}{2^{(n-1)^2}}$ ，故 $\frac{f_n}{2^{n-1}f_{n-1}}=\frac{2^n-1}{2^{2n-1}}$ 。最终得到 $f_{n}=\left(1-\frac{1}{2^n}\right)f_{n-1}$ ，已知 $f_1=\frac{1}{2}$ 。预处理 $2$ 的幂的逆元后，即可 $O(n)$ 得到 $f_n$ 的值，再处理 $f_n$ 的异或前缀和，每次查询 $O(1)$ 输出答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第六场） Problem B
Date: 8/26/2020
Description: Liner Algebra, Probability Theory
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int N=20000000;
int _;
ll f[N+2];
ll inv2[N+2];
ll ans[N+2];
int n;
void init();
ll qpow_mod(ll,ll);
int main(){
    init();
    for(cin>>_;_;_--){
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}
void init(){
    int i;
    inv2[1]=qpow_mod(2,mod-2);
    //inv(2^n)=inv(2)^n
    for(i=2;i<=N;i++){
        inv2[i]=inv2[i-1]*inv2[1]%mod;
    }
    f[1]=inv2[1];
    for(i=2;i<=N;i++){
        f[i]=(1-inv2[i]+mod)*f[i-1]%mod;
    }
    ans[1]=f[1];
    for(i=2;i<=N;i++){
        ans[i]=f[i]^ans[i-1];
    }
}
ll qpow_mod(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}