正題
題目連結:https://www.luogu.com.cn/problem/CF388D
題目大意
給出\(k\)，求有多少個集合\(S\)滿足\(S\sube [1,k]\)且
\[a\in S,b\in S\Rightarrow a\ xor\ b\in S
\]
\(1\leq k\leq 10^9\)
解題思路
發現這個性質和線性基的很像，問題可以轉換為問有多少個本質不同的線性基最大異或和不超過\(k\)。
在我們求\(k\)大異或和的時候我們把所有相同的線性基轉換成了一個相同的形式滿足對于它的數組\(d\)：
- \(d_i\)如果不是零那麼其第\(i\)位是\(1\)且對于所有\(j\neq i\)都有\(d_j\)的第\(i\)位為\(0\)。
此時統計這種線性基的數量就不會算重了，并且全部的\(d\)異或起來一定是最大的。
然後然後就\(dp\)了，設\(f_{i,j,0/1}\)表示到二進制第\(i\)位，前面有\(j\)個\(d\)不是\(0\)，現在的異或和的前\(i\)位到達/每到達\(k\)的上限。
轉移的時候對于一位\(d\)，如果填\(0\)那麼就需要考慮前面的\(d\)有多少個加上這一位。為了友善轉移可以預處理一下\(g_i\)表示\(i\)個東西選出奇數個的方案就好了。
時間複雜度\(O(\log^2 k)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll P=1e9+7,N=35;
ll n,ans,f[N][N][2],C[N][N],g[N];
signed main()
{
C[0][0]=1;
for(ll i=1;i<N;i++)
for(ll j=0;j<=i;j++)
C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
for(ll i=1;i<N;i++)
for(ll j=1;j<=i;j+=2)g[i]+=C[i][j];
scanf("%lld",&n);f[30][0][1]=1;
for(ll i=29;i>=0;i--)
for(ll j=0;j<30-i;j++){
if((n>>i)&1){
(f[i][j+1][1]+=f[i+1][j][1]%P)%=P;
(f[i][j][1]+=f[i+1][j][1]*g[j]%P)%=P;
(f[i][j+1][0]+=f[i+1][j][0]%P)%=P;
(f[i][j][0]+=f[i+1][j][0]*(1ll<<j)%P+f[i+1][j][1]*((1ll<<j)-g[j])%P)%=P;
}
else{
(f[i][j][1]+=f[i+1][j][1]*((1ll<<j)-g[j])%P)%=P;
(f[i][j+1][0]+=f[i+1][j][0]%P)%=P;
(f[i][j][0]+=f[i+1][j][0]*(1ll<<j)%P)%=P;
}
}
for(ll j=0;j<30;j++)(ans+=f[0][j][0]+f[0][j][1])%=P;
printf("%lld\n",ans);
return 0;
}