[校内训练19_09_03]c Huge Counting

题意

有一个定义在 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)}$

$1leq 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         else
100             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 }

View Code