題意

有一個定義在 k 維非負整點上的函數:$f(x_1,x_2,...,x_k):N_{0}^{k}->\{0,1\}$ ,定義方法如下:

若存在$j∈[1,k],x_j=0$,則$f(x_1,x_2,...,x_k)=0$

若對$j∈[1,k]$都有$x_j=1$則$f(x_1,x_2,...,x_k)=1$

否則$f(x_1,x_2,...,x_k)=(\sum_{j=1}^{k}{f(x_1,...,x_{j-1},x_j-1,x_{j+1},...,x_k)})mod 2$

現在給出k,并對每一維坐標給出區間$l_i,r_i$,求:

$\sum_{x_1∈[l_1,r_1],...,x_k∈[l_k,r_k]}{f(x_1,x_2,...,x_k)}$

$1\leq T \leq 10,1 \leq k \leq 9,1 \leq l_j,r_j \leq 10^{15}$。

思考

對于k,某個點的f值為1的充要條件是所有維度在二進制表示下沒有交集,即$x_i\&x_j=0,i≠j$。

由于每個維度都有一個限制,不好算,因此我們容斥每個維度是否滿足限制。這樣,問題轉化為選k個數,第i個數最多能選$a_i$個,每一個二進制位上最多有一個1的方案數。設f[i][0/1][S]表示從高位到低位填到第i個數,0/1是當前有沒有選1,S是k個數是否達到上限的方案數。每次轉移時,考慮當前這一位填不填1即可。

復雜度$O(T*2^{(2k)}*n)$,需要卡常。

代碼

  1 // luogu-judger-enable-o2  2 #define mod 990804011  3 #include<bits/stdc++.h>  4 using namespace std;  5 typedef long long int ll;  6 int T;  7 int k;  8 ll ans,L[55],R[55];  9 ll f[55][2][1<<9]; 10 bool vis[1<<9][1<<9]; 11 int BASE,dig[55]; 12 int d[55]; 13 struct node 14 { 15     int S1,S2; 16     ll val; 17     node(int a=0,int b=0,ll c=0):S1(a),S2(b),val(c){} 18 }; 19 inline ll get(ll S,ll x) 20 { 21     return (S&((ll)(ll)1<<x))>0; 22 } 23 inline ll newlimit(ll D,ll nowD,ll limit) 24 { 25     return ((D^nowD)^(BASE))&limit; 26 } 27 inline ll max(ll x,ll y) 28 { 29     return x>y?x:y; 30 }  31 inline ll calc(int S) 32 { 33     ll maxx=0; 34     for(int i=0;i<=51;++i) 35         dig[i]=0; 36     for(int i=0;i<k;++i) 37     { 38         if(S&((ll)1<<i)) 39         { 40             if(L[i]==0) 41                 return 0; 42             for(int j=0;j<=51;++j) 43                 dig[j]|=get(L[i]-1,j)<<i; 44             maxx=max(maxx,L[i]); 45         } 46         else 47         { 48             for(int j=0;j<=51;++j) 49                 dig[j]|=get(R[i],j)<<i; 50             maxx=max(maxx,R[i]); 51         } 52     } 53     int base=log2(maxx)+2; 54     memset(f,0,sizeof(f)); 55     f[base][0][(1<<k)-1]=1; 56     for(register int i=base;i>=1;--i) 57     { 58         for(register int S=0;S<(1<<k);++S) 59             if(f[i][0][S]) 60             { 61                 register int x=newlimit(dig[i-1],0,S); 62                 f[i-1][0][x]=(f[i-1][0][x]+f[i][0][S])%mod; 63             } 64         for(register int S=0;S<(1<<k);++S) 65             if(f[i][1][S]) 66             { 67                 register int x=newlimit(dig[i-1],0,S); 68                 f[i-1][0][x]=(f[i-1][0][x]+f[i][1][S])%mod; 69             } 70         for(register int S=0;S<(1<<k);++S) 71             if(f[i][1][S]) 72                 for(register int d1=0;d1<k;++d1) 73                     if(get(S,d1)==0||get(dig[i-1],d1)==1) 74                     { 75                         register int x=newlimit(dig[i-1],1<<d1,S); 76                         f[i-1][1][x]=(f[i-1][1][x]+f[i][1][S])%mod; 77                     } 78         for(register int S=0;S<(1<<k);++S) 79             if(f[i][0][S]) 80                 for(register int d=0;d<k;++d) 81                     if(get(S,d)==0||get(dig[i-1],d)==1) 82                     { 83                         register int x=newlimit(dig[i-1],1<<d,S); 84                         f[i-1][1][x]=(f[i-1][1][x]+f[i][0][S])%mod; 85                     } 86     } 87     ll sum=0; 88     for(register int S=0;S<(1<<k);++S) 89         sum=(sum+f[0][0][S]+f[0][1][S])%mod; 90     return sum; 91 } 92 void dfs(int s,int S,int G) 93 { 94     if(s==k) 95     { 96         ll x=calc(S); 97         if(G&1) 98             ans=(ans-x+mod)%mod; 99         else100             ans=(ans+x)%mod;101         return;102     }103     dfs(s+1,S,G);104     dfs(s+1,S|((ll)1<<s),G+1);105 }106 inline void solve()107 {108     cin>>k;109     for(int i=0;i<k;++i)110     {111         cin>>L[i]>>R[i];112         --L[i],--R[i];113     }114     ans=0;115     BASE=((ll)1<<k)-1;116     dfs(0,0,0);117     cout<<ans<<endl;118 }119 int main()120 {121     ios::sync_with_stdio(false);122     cin>>T;123     while(T--)124         solve();125     return 0;126 }