2020牛客第六场 B题 Binary Vector

题意 求1/2 3/4 7/8

每一项累乘的异或 ，除法用逆元去算

pow（x,p-2)每次要log

然后发现分母每次是乘2的 就是 2  4  8  16 32 ，发现每次只要多除一次2就行了，那就多乘一次逆元

然后线性处理一下逆元前缀和就可以了

这题比较绕，前缀套前缀

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
const long long mod=1e9+7;
const int maxn=2e7+5;
ll ans[maxn];
int main()
{
   long long t;
   cin>>t;

   ll inv=500000004;
   ll b=500000004;
   ans[0]=1;
   int pre=2;
   for(int i=1;i<=2e7;i++){
    ans[i]=(ans[i-1]*(pre-1)%mod)*inv%mod;
    inv=inv*b%mod;
    pre=pre*2%mod;
   }
   for(int i=2;i<=2e7;i++)
    ans[i]^=ans[i-1];

   while(t--)
   {
      int n;
      cin>>n;
      cout<<ans[n]<<endl;
   }
}