题目描述
在一个(k)维空间中，每个整点被黑白染色。对于一个坐标为((x_1,x_2,ldots,x_k))的点，他的颜色我们通过如下方式计算：
- 如果存在一维坐标是(0)，则颜色是黑色。
- 如果这个点是((1,1,ldots,1))（每一维都是(1)），这个点的颜色是白色
- 如果这个点的(k)个前驱（任取一维坐标减(1)）中的白点有奇数个，那么这个点的颜色就是白色，否则就是黑色
给出一个(k)维超矩形，求这个矩形内的白点个数。
(kleq 9,1leq l_ileq r_ileq {10}^{15})
题解
先把所有坐标(-1)。
然后DP。
设(S=(x_1,x_2,ldots,x_k))。
设(f_S)为一个坐标为(S)点的颜色（(1)为白色，(0)为黑色）。
(f_S=f_{S_1}oplus f_{S_2}oplus cdots oplus f_{S_k})。其中(S_1,S_2,ldots,S_k)为(S)的(k)个前驱。
这个表达式同样可以看成(f_S=(sum_{i=1}^k f_{S_i})mod 2)。
那么可以看出(f_S)就是从((0,0,ldots,0))走到(S)的方案数(mod 2)，就是(inom{x_1+x_2+cdots+x_k}{x_1~x_2~cdots~x_k}mod 2)。
我们推广一下卢卡斯定理，就会发现(f_S=1)当且仅当(x_1,x_2,ldots,x_k)之间两两and和为(0)。
可以用数位DP计算这个东西。
时间复杂度：(O(3^{log r}))
我偷懒写了(O(4^{log r}))的做法。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
int n,s;
pii a[110];
int f[110][110][110];
int xx[110];
int yy[110];
int m1,m2;
int d[110];
int gao(int x)
{
return x?s/x:0x3fffffff;
}
int gao(int l,int r,int h)
{
int &s=f[h][l][r];
if(~s)
return s;
while(l<=r&&d[l]<=h)
l++;
while(l<=r&&d[r]<=h)
r--;
if(l>r)
return s=0;
int i;
s=0x7fffffff;
for(i=l;i<r;i++)
s=min(s,gao(l,i,h)+gao(i+1,r,h));
int hh=gao(xx[r]-xx[l]);
if(hh<=yy[h])
return s;
int v=upper_bound(yy+1,yy+m2+1,hh)-yy-1;
s=min(s,gao(l,r,v)+1);
return s;
}
void solve()
{
scanf("%d%d",&n,&s);
int i;
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
xx[i]=a[i].first;
yy[i]=a[i].second;
}
sort(xx+1,xx+n+1);
sort(yy+1,yy+n+1);
m1=unique(xx+1,xx+n+1)-xx-1;
m2=unique(yy+1,yy+n+1)-yy-1;
memset(f,-1,sizeof f);
for(i=1;i<=m1;i++)
d[i]=0;
for(i=1;i<=n;i++)
{
a[i].first=lower_bound(xx+1,xx+m1+1,a[i].first)-xx;
a[i].second=lower_bound(yy+1,yy+m2+1,a[i].second)-yy;
d[a[i].first]=max(d[a[i].first],a[i].second);
}
int ans=gao(1,m1,0);
printf("%d
",ans);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}