原题链接：https://ac.nowcoder.com/acm/contest/5671/B

线性独立相关概念：https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E7%8B%AC%E7%AB%8B

题目描述

设A={0,1}，某无聊透顶的神每天从图片说明 （即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。答案输出同该场比赛中有大Van题的有些许错误的A题相似。其中本题的模数为1e9+7。

输入描述

第一行输入一个T，表示测试样例的数目；
接下来的T行每行输入一个数N。

输出描述

对于每个样例输出一个答案。

样例

  • 输入
    3
    1
    2
    3
  • 输出
    500000004
    194473671
    861464136

说明：

f(1)=图片说明

f(2)=图片说明

f(3)=图片说明

题解思路

这道题目奇葩地牵涉到了向量，所以需要先了解何为线性独立。所谓线性独立，就是每个向量都不共面，即向量之间不能直接通过加减得到。
首先我们可以考虑每个维度分别有多少向量。
不难发现，第一维度仅有0,1这两个向量，而二维则有（0,0），（0,1），（1,0），（1,1）这四个变量……………………以此类推，不难发现第n维共有图片说明 个向量。
一通计算猛如虎，发现取i个向量时，对于i，有图片说明 个向量不与选择的向量独立。
接下来很容易不难得出，在n维的空间里，选取i个向量各自独立的概率为图片说明 ，
所以，图片说明 图片说明 ;
看着这一大坨一定很头疼，经化简后却变成了：
图片说明 图片说明 图片说明 图片说明
晓得了公式，那么打表就不成问题了。

参考代码

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

long long Mod=1e9+7;
long long m=2,f1[20000055],p1=500000004,p=500000004,f;

int main()
{
    f=f1[1]=p;
    for(int i=2;i<=20000050;i++)
    {
        m=m*2%Mod;
        p1=p1*p%Mod;
        f=f%Mod*(m-1)%Mod*p1%Mod;
        f1[i]=f1[i-1]^f;
    }
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%lld\n",f1[n]);
    }
}