[51Nod 1301] 集合异或和 (dp)

Solution

一道比较好的dp题想了半天组合数QAQ

首先要知道的是 A<B一定是B有一位是1且A的这位是0且前面都相等

那么肯定是要枚举这一位在哪里然后求出方案数

方案数考虑类似背包的方法分三种情况转移具体见代码

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

typedef long long LL;

const int N=5000,MOD=1e9+7;

int n,m;

LL ans,f[2][N][2];

int main() {

	cin>>n>>m;

	for(int i=0;(1<<i)<=max(n,m);i++) {

		memset(f,0,sizeof(f));

		f[0][0][0]=1;

		for(int j=1;j<=max(n,m);j++) {

			int x=(j>>i)&1,c=j&1;

			for(int k=0;k<=2048;k++) F(X,0,1) {

				f[c][k][X]=f[c^1][k][X];

				if(j<=n) f[c][k][X]=(f[c][k][X]+f[c^1][k^j][X])%MOD;

				if(j<=m) f[c][k][X]=(f[c][k][X]+f[c^1][k^j][X^x])%MOD;

			}

		}

		F(j,(1<<i),(1<<(i+1))-1) ans=(ans+f[(max(n,m)&1)][j][1])%MOD;

	}

	printf("%lld",ans%MOD);

	return 0;

}

巴特西

[51Nod 1301] 集合异或和 (dp)

Solution

Code

最新文章

热门文章