首页 > 其他分享 >[CCPC2022 广东] XOR Sum

[CCPC2022 广东] XOR Sum

时间:2024-07-21 14:56:10浏览次数:13  
标签:cnt CCPC2022 XOR int Sum i64 dep return left

数位 dp

看到这样求和价值的计算,考虑可不可以交换求和符号或者改变计算方式。

这题中的位运算使我们考虑按位计算贡献,价值可以写成:

\[f(A)=\sum_{i=0}2^i\times c_i\times (k-c_i) \]

其中 \(c_i\) 表示第 \(i\) 位上为 \(1\) 的 \(a_i\) 数量。

题目第二个要求即 \(f(A)=n\)。考虑从高位到低位计算贡献,类似数位 dp 计算方案数。于是序列中的元素就分为两种:卡了上界和没卡上界的。并且计算到当前位时需要知道低位留下来的余数,使该位最终与 \(n\) 上这一位相同。

设 \(dp(i,j,k)\) 表示考虑完从高到低前 \(i\) 位,此时低位留下的余数为 \(j\),卡了上界的数的数量为 \(k\) 的方案数。

转移看 \(m\) 上第 \(i\) 位上是 \(0\) 还是 \(1\):

如果是 \(0\),那么卡上界的数只能继续卡上界,枚举没卡上界的数中 \(1\) 的个数。

如果是 \(1\),分别枚举卡上界和不卡上界的 \(1\) 的个数。

\(1\) 的位置不固定,所以需要预处理组合数。

记忆化搜索即可。

分析当前位上余数最多是多少,如果余数 \(cnt\) 满足 \((cnt-81)\times 2\ge cnt\),那么低位上不存在一种方案使得出现这样的余数。

复杂度 \(O(50\times162\times18\times18\times 18)\),远小于此数。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 50, M = 170, K = 19, mod = 1e9 + 7;
i64 n, m, k;
i64 f[N][M][K], a[N], c[K][K];
i64 dfs(int dep, int left, int cnt) {
	if(left >= 162) return 0;
	if(dep == -1) return left == 0;
	if(f[dep][left][cnt] != -1) return f[dep][left][cnt];
	int dig = (!dep ? 0 : ((n >> (dep - 1)) & 1));
	i64 ans = 0;
	if(!a[dep]) {
		for(int i = 0; i <= k - cnt; i++) {
			int cur = left - 1LL * i * (k - i);
			if(cur < 0) continue;
			ans = (ans + c[k - cnt][i] * dfs(dep - 1, (cur << 1) | dig, cnt) % mod) % mod;
		}
	} else {
		for(int i = 0; i <= cnt; i++) {
			for(int j = 0; j <= k - cnt; j++) {
				int cur = left - 1LL * (i + j) * (k - j - i);
				if(cur < 0) continue;
				ans = (ans + c[cnt][i] * c[k - cnt][j] % mod * dfs(dep - 1, (cur << 1) | dig, i) % mod) % mod;
			}
		}
	}
	f[dep][left][cnt] = ans;
	return ans;
}
int solve() {
	if(k == 1) return !n;		
	if(!m) return !n;
	memset(f, -1, sizeof(f));
	i64 l = 0, left = 0;
	while(m) {
		a[l++] = m % 2;
		m >>= 1;
	}
	for(int i = l; i <= 50; i++) {
		if((n >> i) & 1) {
			left += (1LL << (i - l));
		}
	}
	if(left >= 162) return 0;
	return dfs(l, left, k);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n >> m >> k;

	c[0][0] = 1;
	for(int i = 1; i <= k; i++) {
		c[i][0] = 1;
		for(int j = 1; j <= i; j++) {
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
	std::cout << solve() << "\n";

	return 0;
}

标签:cnt,CCPC2022,XOR,int,Sum,i64,dep,return,left
From: https://www.cnblogs.com/FireRaku/p/18314467

相关文章

  • A. Sum of Three
    原题链接题解要让abc不同,我们可以先固定ab取两个较小值,然后看看最大的c有没有重复code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;voidsolve(){intn;cin>>n;if(n<7){cout<<"NO\n";return;}......
  • F. Equal XOR Segments
    链接https://codeforces.com/problemset/problem/1968/F题目思路感觉这是一道非常好的区间异或结论题!思路参考大佬题解值得总结的:1.区间异或的可加性:^[la,ra]==^[ra+1,rb]-->^[1,ra]==^[1,rb]2.aaa=a,用来消除过长的异或.虽然刚开始想用线段树,但是没法实现判断如何实......
  • [ARC173E] Rearrange and Adjacent XOR 题解
    题目链接点击打开链接题目解法太牛了!!!这道题我的第一反应是从高位往低位确定,但这样就全错了换个角度考虑,找最后的答案可以由那些数异或而成这里给出结论:答案一定是偶数个数的异或和(在\(n\%4=2\)且\(n\neq2\)时,不能由全集构成)证明:选出的数非全集的情况用数学归纳法......
  • SMU Summer 2024 Contest Round 5
    SMUSummer2024ContestRound5RobotTakahashi思路按照Wi......
  • SMU Summer 2024 Contest Round 5
    ARobotTakahashi思路:将所有数排序,枚举孩子成人的分解点X,同时根据s的标识维护正真的孩子成人的个数voidsolve(){intn;cin>>n;strings;cin>>s;intsum=0;for(inti=0;i<s.size();++i){if(s[i]=='1')sum++;......
  • D. Maximum Sum of Products
    链接https://codeforces.com/problemset/problem/1519/D题目分析总的来说不算难的一道题,主要是敢写就行,控制在O(n^2),枚举中心点,分成两类:一类是奇数,一类是偶数对称就行。代码#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<vector>#include<algorithm>#in......
  • [GWCTF 2019]xxor
    64位,进ida第一个for循环,输入六个32位字符串,转换成整数,存到v6数组第二个for循环,函数是把低位和高位分成了两个dword,就是在一个循环中一下处理了两个数据(两个32位数据在64位数组中)然后看看这个unk_601060,32位对齐,所以里面的数据就是(2,2,3,4)接下来就是sub_400686这个加密函数可......
  • java8四个函数式接口:Function, Predicate, Consumer, Supplier使用
    目录1、前言2. 四大函数式接口1.Function,>2.Predicate 3.Consumer4.Supplier1、前言Java8引入了一种新的接口特性,叫做函数式接口。这种接口只能有一个抽象方法,通常用注解@FunctionalInterface标识。函数式接口可以被隐式地转换为lambda表达式。以下是一个......
  • SMU Summer 2024 Contest Round 4
    1.HandV原题链接:http://162.14.124.219/contest/1008/problem/B二进制枚举行列即可查看代码#include<bits/stdc++.h>#defineintlonglong#definePIIpair<int,int>usingnamespacestd;intn,m,k;chara[10][10];signedmain(){ios::sync_with_stdio(fals......
  • SMU Summer 2024 Contest Round 4
    AMadeUp思路:统计A的个数,O(1)统计cnt[bc]voidsolve(){intn;cin>>n;vector<int>cnt(n+1),b(n+1);for(inti=1;i<=n;++i){intx;cin>>x;cnt[x]++;}for(inti=1;i<=......