[C++知识库]#757 (Div. 2) C（位运算+推式子 D1（dp

C. Divan and bitwise operations
题意：
给定一个长度为 $n$ 的非负整数序列，$m$ 个条件，每次给定区间 $[l,r]$，以及这段区间所有数的或起来的值 $x$。求所有该序列所有子序列的异或和
思路：
题解
题解中 $C$ 讲的很好理解
首先先明确长度为 $n$ 的序列，子序列有多少个，对于每个数选或不选，显然有 $2^n$ 个子序列，其中包括了空子序列
把每一位分开考虑
设第 $i$ 位有 $k$ 个 $1$，则有 $n?k$ 个 $0$
一个子序列对答案有贡献，需要满足第 $i$ 位有奇数个 $1$
结合二项式定理，第 $i$ 位有奇数个 $1$ 的子序列的个数： $2^{(n?k)}?(C_k^1+C_k^3+...+C_k^{last})=2^{n?k}?2^{k?1}=2^{n?1}$
可以发现答案与 $k$ 无关，某一位对答案是否有贡献取决于该位有没有 $1$
有 $1$ 则会贡献 $2^i?2^{n?1}$
这个时候答案就很显然了，把所有 $x$ 或一遍，
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
ll q_pow(ll a, ll b){
	ll ans = 1;
	while(b){
		if(b & 1) ans = ans * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}
void work()
{
	cin >> n >> m;
	ll ans = 0;
	for(int i = 1, l, r, x; i <= m; ++i){
		cin >> l >> r >> x;
		ans |= x;
	}	
	cout << ans % mod * q_pow(2, n - 1) % mod << endl;
}

int main()
{
	ios::sync_with_stdio(0);
	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

D1. Divan and Kostomuksha (easy version)
题意：
给定一个正整数序列，现在可以对该序列进行任意排序，使得下列式子最大化
$$\sum _{i=1}^{n}gcd(a_1,a_2,...a_i)$$
思路：
考虑 $dp$
$dp[i]$ 表示把 $gcd$ 为 $i$ 的数放最前时的答案，此时这组数的先后顺序不论, 但是一定是排在其他数之前的.
$d[i]$ 表示含有因子 $i$ 的数的数量
状态转移方程
$$dp[i]=\underset{j|i}{\max }(dp[j]+d[i]?(i?j))$$
用类似线性筛的方法转移
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 5e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int d[maxn];
ll dp[maxn];
void f(int x){
	for(int i = 1; i * i <= x; ++i) if(x % i == 0)
	{
		d[i]++;
		if(i * i != x) d[x/i]++;
	}
}
void work()
{
	cin >> n;
	for(int i = 1, x; i <= n; ++i) cin >> x, f(x);
	ll ans = n;
	dp[1] = n;
	for(int i = 1; i <= maxn - 9; ++i)
	{
		ans = max(ans, dp[i]);
		for(int j = 2; j * i <= maxn - 9; ++j)
		{
			dp[i * j] = max(dp[i * j], dp[i] + 1ll * d[i * j] * (i * j - i));
		}
	}
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}