首页 > 代码库 > uva 1489 - Math teacher's homework(数位dp)
uva 1489 - Math teacher's homework(数位dp)
题目链接:uva 1489 - Math teacher‘s homework
题目大意:给定n,k,以及序列m1,m2,…,mn, 要求找到一个长度为n的序列,满足0<=xi<=mi, 并且x1XORx2XOR…XORxn=k
解题思路:数位dp,在网上看了别人的代码,高大上。。。
假设有二进制数 k : 00001xxxx mi:0001xxxxx, 那么对于xi即可以满足任意的x1XORx2XOR…XORxi?1XORxi+1XOR…XORxn,根据这一点进行数位dp。
dp[i][j]表示在第i个数,对于当前位是由j个1没有使用的。
特别对于dp[i][1] = dp[i][1] + dp[i-1][0], 因为dp[i-1][0]是没有1可以用的,即使不满足说随便添加数都是可以的,所以不能乘以bits。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 55;
const ll MOD = 1000000003LL;
ll N, K;
ll dp[maxn][maxn], num[maxn];
int main () {
while (scanf("%lld%lld", &N, &K) == 2 && (N + K)) {
ll ans = 0;
for (int i = 1; i <= N; i++)
scanf("%lld", &num[i]);
int bit;
for (bit = 30; bit >= 0; bit--) {
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
ll cnt = 0, bits = (1<<bit);
for (int i = 1; i <= N; i++) {
if (num[i]&bits) {
cnt++;
for (int j = 0; j <= cnt; j++)
dp[i][j] = dp[i-1][j] * (num[i] - bits + 1) % MOD;
dp[i][1] = (dp[i][1] + dp[i-1][0]) % MOD;
for (int j = 2; j <= cnt; j++)
dp[i][j] = (dp[i-1][j-1] * bits + dp[i][j]) % MOD;
num[i] -= bits;
} else {
for (int j = 0; j <= cnt; j++)
dp[i][j] = dp[i-1][j] * (num[i] + 1) % MOD;
}
}
for (int i = 1; i <= cnt; i++)
if ( ((cnt - i)&1) == ((K>>bit)&1) )
ans = (ans + dp[N][i]) % MOD;
if ( (cnt&1) != ((K>>bit)&1) )
break;
}
if (bit == -1)
ans++;
printf("%lld\n", ans);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。