题目

题目大意自己看题去……

正解

比赛时在刚第二题，所以根本没有时间思考……

模型可以转化为从\((x_1,x_2,..,x_n)\)出发到\((1,1)\)的方案数模\(2\)。

方案数就用有重复的排列公式：\(\frac{(\sum{x_i})!}{\prod x_i!}\)

考虑它的奇偶性。显然可以将上面的\(2\)因子个数求出来，减去下面的个数，如果为\(0\)则是奇数。

这个东西也就是下面这条式子：\(\sum_{w=2^i} (\lfloor \frac{\sum_{x_i}}{w} \rfloor-\sum{\lfloor \frac{x_i}{w}\rfloor})\)

显然这条式子是大于等于\(0\)的。我们考虑它是否等于\(0\)。

然后我们就发现，如果有相加的时候有进位，那么它就会对下一位有贡献，而这一位的贡献不变。这意味着上式的值至少加\(1\)。

所以，若要它等于\(0\)，一定要保证相加的时候没有进位，也就是每一位上为\(1\)的数至多有\(1\)个。

于是就开始DP：设\(f_{i,S}\)表示从高到低到\(i\)位，\(S\)为贴着上限的状态。

由于有上下界的限制，所以容斥一下就可以了。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mo 990804011

#define ll long long

#define N 9

int n;

ll l[N],r[N],lim[N];

ll ans;

ll f[51][512];

inline void upd(ll &a,ll b){a=(a+b)%mo;}

inline ll calc(){

	memset(f,0,sizeof f);

	f[50][(1<<n)-1]=1;

	for (int i=50;i>=1;--i)

		for (int j=0;j<1<<n;++j){

			if (!f[i][j])

				continue;

			int s=0;

			for (int l=0;l<n;++l)

				if (j>>l&1 && !(lim[l]>>i-1&1))

					s|=1<<l;

			upd(f[i-1][s],f[i][j]);

			for (int k=0;k<n;++k)

				if (j>>k&1 && lim[k]>>i-1&1 || !(j>>k&1)){

					int s_=s&((-1)^1<<k) | ((j>>k&1 && lim[k]>>i-1&1)?1<<k:0);

					upd(f[i-1][s_],f[i][j]);

				}

		}

	ll res=0;

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

		res+=f[0][i];

	return res%mo;

}

void dfs(int k,int flag){

	if (k==n){

		ans+=calc()*flag;

		return;

	}

	lim[k]=r[k];

	dfs(k+1,flag);

	if (l[k]-1>=0){

		lim[k]=l[k]-1;

		dfs(k+1,-flag);

	}

}

int main(){

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	int T;

	scanf("%d",&T);

	while (T--){

		scanf("%d",&n);

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

			scanf("%lld%lld",&l[i],&r[i]),l[i]--,r[i]--;

		ans=0;

		dfs(0,1);

		ans%=mo;

		ans=(ans<0?ans+mo:ans);

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

	}

	return 0;

}

总结

坦白说我的脑子真是太不好了……

巴特西

[JZOJ6344] 【NOIP2019模拟2019.9.7】Huge Counting

题目

正解

代码

总结

最新文章

热门文章