BZOJ 2734 洛谷 3226 [HNOI2012]集合选数【状压DP】【思维题】

时间:2024-09-05 09:06:02

BZOJ 2734 洛谷 3226 [HNOI2012]集合选数【状压DP】【思维题】

【题解】

  思维题,看了别人的博客才会写。

  写出这样的矩阵:

  1,3,9,...

  2,6,18,...

  4,12.36,...

  8,24,72,...

  我们要做的就是从矩阵中选出一些数字,但是不能选相邻的。

  我们可以发现,在100000的范围内,这个矩阵最多只有18行,11列。

  那么这个矩阵的取数字的方案数直接状压DP即可。f[i][j]表示第i行,状态为j的方案数,转移就是f[i][j]=sigma(f[i-1][k]) ,条件是(j&k==0且k&(k>>1)==0)

  但是这个矩阵不能覆盖值域之内的所有数字,怎么办呢?我们可以找到最小的没有被覆盖的数,用它放在(1,1)的位置构造一个类似的矩阵。

  可以证明每个数字恰好在矩阵中出现一次。所以最终答案就是各个矩阵的答案相乘。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define N 50
#define MOD(x) ((x)>=mod?(x)-mod:(x))
using namespace std;
const int mod=;
int n,ans=,a[N][N],mx[N],f[N][],exp[N];
bool vis[];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
} inline int calc(int x){
memset(mx,,sizeof(mx)); memset(f,,sizeof(f));
a[][]=x;
for(rg int i=;i<=;i++)a[i][]=(a[i-][]*<=n)?a[i-][]<<:n+;
for(rg int i=;i<=;i++)
for(rg int j=;j<=;j++) a[i][j]=(a[i][j-]*<=n)?a[i][j-]*:n+;
for(rg int i=;i<=;i++)
for(rg int j=;j<=;j++)if(a[i][j]<=n){
mx[i]+=exp[j-];
vis[a[i][j]]=;
}
f[][]=;
for(rg int i=;i<=;i++)
for(rg int j=;j<=mx[i];j++)if(!(j&(j>>)))
for(rg int k=;k<=mx[i-];k++)if(!(j&k)&&!(k&(k>>)))
f[i][j]=MOD(f[i][j]+f[i-][k]);
return f[][];
}
int main(){
exp[]=; for(rg int i=;i<;i++) exp[i]=exp[i-]<<;
n=read();
for(rg int i=;i<=n;i++)if(!vis[i]) ans=(1ll*ans*calc(i))%mod;
printf("%d",ans);
return ;
}