题解：
t1:
题解是循环矩阵
但我并没有往矩阵上想下去。。。
这个东西比较显然的是可以把它看成生成函数
然后就可以任意模数fft了
复杂度比题解优 $nlog^2$
t2:
随便推推式子就好了
t3:
矩阵的一般套路
维护$f(n-1),f(n-2),{f(n-1)}^2,{f(n-2)}^2,f(n-1)*f(n-2)$
他们之间是可以递推的
t4:不会
t5:
这种题目比较显然是找规律
然后会发现2^i-2^i+1的差是等差数列
暴力做是nlogn的
我们可以利用一些优化做到O(n)
对2^n的打表（当然我oeis了一下是有递推式的）
然后快速查某个数有几位（builtin 但noi赛事都不能用于是我就手动实现了）
然而这题空间开16m不知道意义何在
fread的快读和快输都不能用。。。
不用快读快输显然过不了
还得从网上拉了个getchar的。。很烦。。
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (int i=h;i<=t;i++) #define dep(i,t,h) for (int i=t;i>=h;i--) #define ll long long namespace IO{ /* char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T>void read(T &x) { rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; }*/ char sr[1<<24],z[20];int C=-1,Z=0; template<class T>void wer(T x) { if (x<0) sr[++C]='-',x=-x; while (z[++Z]=x%10+48,x/=10); while (sr[++C]=z[Z],--Z); } IL void wer1() {sr[++C]=' ';} IL void wer2() {sr[++C]=' ';} }; using namespace IO; const int mo=1e9+7; int wa[100000]; ll p[70]={0,0ll, 2ll, 14ll, 70ll, 310ll, 1302ll, 5334ll, 21590ll, 86870ll, 348502ll, 1396054ll, 5588310ll, 22361430ll, 89462102ll, 357881174ll, 431590223ll, 726491955ll, 906229948ll, 625444057ll, 502824788ll, 13396288ll, 57779454ll, 239506422ll, 974802902ll, 932766017ll, 798172909ll, 326909341ll, 576072811ll, 841162140ll, 438390354ll, 901045041ll, 899147409ll, 186524142ll, 925965631ll, 63600624ll, 973878754ll, 334467499ll, 215775006ll, 618910060ll, 987260307ll, 972281364ll, 935605751ll, 835383617ll, 527455717ll, 481665396ll, 670346656ll, 168756770ll, 649767409ll, 548550282ll, 93162436ll, 170572390ll, 278134854ll, 304230006ll, 600301213ll, 167967225ll, 205393676ll, 888624265ll, 688596163ll, 22582881ll, 626728026ll}; IL int getws(ll x) { if (x>>48) return 48+wa[x>>48]; if (x>>32) return 32+wa[x>>32]; if (x>>16) return 16+wa[x>>16]; return wa[x]; } IL ll js(ll x) { int k=getws(x); ll now=1ll<<(k-1); return (p[k-1]+((x-now)%mo)*((x-now+1)%mo)%mo)%mo; } ll read(){ ll w=1,q=0;char ch=' '; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar(); return w*q; } void write(ll x) { if(x<0){putchar('-');x=~(x-1);} int s[20],top=0; while(x){s[++top]=x%10;x/=10;} if(!top)s[++top]=0; while(top)putchar(s[top--]+'0'); } int main() { freopen("1.in","r",stdin); freopen("2.out","w",stdout); rep(i,1,65538) wa[i]=wa[i>>1]+1; int n; ios::sync_with_stdio(false); n=read(); rep(i,1,n) { ll k; k=read(); write(js(k)); printf(" "); } return 0; }
t6:
数据范围写成这样出题人真的是nb
首先每个点都可以用组合数表示出来
然后再推推式子就得到全部的了