Binary Vector【公式】-2020牛客暑期多校6

题意：

分析：

当时是根据样例猜出的公式：

[f(n)=frac{prod_{n}^{i=1}{(2^i-1)}}{2^{frac{n(n+1)}{2}}} ]

然后递推求出 (2^n) 的逆元，预处理答案即可。注意超时和超内存。
具体的推导过程：https://blog.csdn.net/qq_45458915/article/details/107625864

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=2e7+5;
ll ans[N],tmp[N],res[N];
ll power(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init()
{
    ll tv=power(2LL,mod-2);
    ll inv=1;
    tmp[1]=2;
    for(int i=2;i<=2e7;i++)
        tmp[i]=tmp[i-1]*2%mod;
    ans[0]=1,res[0]=0;
    for(int i=1;i<=2e7;i++)
    {
        inv=inv*tv%mod;
        ans[i]=(ans[i-1]*(tmp[i]-1+mod)%mod*inv)%mod;
    }
    for(int i=1;i<=2e7;i++)
        res[i]=res[i-1]^ans[i];
}
int main()
{
    int t,n;
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld
",res[n]);
    }
    return 0;
}