【BZOJ4903】【UOJ#300】吉夫特（卢卡斯定理，动态规划）

题面

UOJ

BZOJ：给的UOJ的链接......

题解

首先模的质数更小了，直接给定了\(2\)。当然是卢卡斯定理了啊。

考虑一个组合数在什么情况下会是一个奇数。\(Lucas(n,m)\equiv Lucas(n/2,m/2)*Lucas(n\%2,m\%2)\)。后面这个东西一共只有\(4\)种取值，我们大力讨论一下:\(C_{0}^0=1,C_{0}^1=0,C_1^0=1,C_1^1=1\)。既然是一个奇数，证明\(n,m\)之中不存在任意两个二进制位满足\(n\)是\(0\)，\(m\)是\(1\)，即\(n\ and\ m=n\)。

现在是一个不上升子序列的相邻两个元素的组合数之积都要是奇数，那么两两之间都要满足这个情况。设\(f[i]\)表示以\(i\)结尾的所有不上升子序列的所求式子的和，每次转移的时候找一个合法的值然后暴力转移过来。但是这样子是\(O(n^2)\)的，考虑如何优化。首先值域范围很小，我们可以开桶暴力记答案，然而这个数据范围很巧妙，每次对于每个数，我们需要枚举集合，这样子的复杂度是\(O(3^{log n}=3^{18})\)，完美的\(TLE\)，而\(3^{17}\)的复杂度就是在时间边缘试探。(然而老邬说他\(3^{18}\)大力艹过去了)，然而我暴力也过去了。

根据二进制毒瘤做法，我们把二进制数拆分成前一半\(9\)位和后一半\(9\)位，先暴力枚举前\(9\)位，然后对于后\(9\)位再做子集枚举，这样子复杂度就瞬间降下来了。

先放暴力AC代码

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 250000*2

#define MOD 1000000007

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int s[MAX],a[MAX],n,f[MAX];

int lg[MAX],mx,ans;

int main()

{

	n=read();

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=1;i<=n;++i)mx=max(mx,a[i]);

	for(int i=2;i<=mx;++i)lg[i]=lg[i>>1]+1;

	for(int i=1;i<=n;++i)

	{

		int p=((1<<(lg[mx]+1))-1)^a[i];f[i]=1;

		for(int t=p;t;t=(t-1)&p)

			add(f[i],s[a[i]|t]);

		add(ans,s[a[i]]=f[i]);add(ans,MOD-1);

	}

	printf("%d\n",ans);

	return 0;

}

按照二进制位折半分，大概比上面的暴力快了\(10\)倍的样子。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

#define MAX 250000

#define MOD 1000000007

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int s[1<<10][1<<10],a[MAX],n,f[MAX];

int lg,mx,ans,llg;

int main()

{

	n=read();for(int i=1;i<=n;++i)mx=max(mx,a[i]=read());

	lg=log2(mx)+1;llg=lg/2;

	for(int i=1;i<=n;++i)

	{

		int p=(1<<(lg-llg))-1;

		int p1=a[i]>>llg,p2=a[i]-(p1<<llg);

		for(int t=p^p1;;t=(t-1)&(p^p1)){add(f[i],s[p1|t][p2]);if(!t)break;}

		for(int t=p2;;t=(t-1)&p2){add(s[p1][t],f[i]+1);if(!t)break;}

		add(ans,f[i]);

	}

	printf("%d\n",ans);

	return 0;

}