# 梦熊J组模拟赛——第二套

## T1 就给你上数学题 (math)

题目等价于让 $a$ 变成 $b$，可以增加奇数，或者减少偶数。显然次数不超过三次，分类讨论即可。

### 情况一：$a$ 小于 $b$

1. 如果 $(b - a)$ 为奇数，那么只需一次操作：
   - 直接将 $a$ 增加 $(b - a)$，即 $a + (b - a) = b$。

2. 如果 $(b - a)$ 为偶数，那么：
   - 如果 $(b - a) / 2$ 为偶数，那么需要两次操作：
     - 第一次操作：将 $a$ 增加一个奇数 $x$ 使得 $a + x$ 变成 $a'$
     - 第二次操作：将 $a'$ 再增加 $x$ 使得 $a' + x = b$

   - 如果 $(b - a) / 2$ 为奇数，那么需要三次操作：
     - 第一次操作：将 $a$ 增加一个奇数 $x$ 使得 $a + x = a'$
     - 第二次操作：将 $a'$ 再增加一个奇数 $x$ 使得 $a' + x = a''$
     - 第三次操作：将 $a''$ 增加一个奇数 $x$ 使得 $a'' + x = b$

### 情况二：$a$ 大于 $b$

1. 如果 $(a - b)$ 为偶数，那么只需一次操作：
   - 直接将 $a$ 减少 $(a - b)$，即 $a - (a - b) = b$。

2. 如果 $(a - b)$ 为奇数，那么需要两次操作：
   - 第一次操作：将 $a$ 增加一个奇数 $x$ 使得 $a + x$ 变成 $a'$
   - 第二次操作：将 $a'$ 再减少 $(a - b + x)$ 的偶数 $y$，使得 $a' - y = b$
   - 具体步骤为：增加一个奇数1，使得$(a + 1 - b)$为偶数，然后减去偶数$(a - b + 1)$即可。

```c++
#include <bits/stdc++.h>
using namespace std;
int T;
int main()
{
    freopen("math.in", "r", stdin);
    freopen("math.out", "w", stdout);
    scanf("%d", &T);
    while(T--)
    {
        int ans = 0;
        int a, b;
        scanf("%d%d", &a, &b);
        if(a == b) ans = 0;
        else if(a < b)
        {
            int d = b-a;
            if(d&1) ans = 1;
            else
            {
                if((d/2)&1) ans = 2;
                else ans = 3;
            }
        }
        else{
            int d = a-b;
            if(d&1) ans = 2;
            else ans = 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}
```

## 部落冲突 (tribe)

使用图的最大独立集算法来解决。在这个问题中，部落的居民可以看作是图中的顶点，居民之间的敌对关系可以看作是图中的边。我们的目标是选择尽可能多的居民，使得他们之间没有边相连，即形成一个最大独立集。

考虑深度优先搜索（DFS），在图中搜索最大独立集。在搜索过程中，需要维护一个集合，记录已经选择的居民，确保选取的居民之间没有敌对关系。

```c++
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int a[110][110],b[110],n,m,u,v,cnt,res1[110],res2[110];
void dfs(int x)
{
	if(x-1>cnt){
		cnt=x-1;
		memset(res2,0,sizeof(res2));
		for(int i=1;i<=cnt;++i)res2[res1[i]]=1;
	}
	for(int i=res1[x-1]+1;i<=n;++i){
		if(!b[i]){
			res1[x]=i;
			++b[i];
			for(int j=1;j<=n;++j)if(a[i][j])++b[j];
			dfs(x+1);
			for(int j=1;j<=n;++j)if(a[i][j])--b[j];
			--b[i];
		}
	}
}

int main()
{
	freopen("tribe.in","r",stdin);
	freopen("tribe.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>u>>v;
		a[u][v]=a[v][u]=1;
	}
	dfs(1);
	cout<<cnt<<endl;
	for(int i=1;i<=n;++i)cout<<res2[i]<<' ';
	return 0;
}
```

## 社交网络服务 (sns.cpp)

### 40 分做法

暴力即可。

遍历所有可能的三元组$(X,Y,Z)$，检查是否满足$X$和$Y$是朋友、$Y$和$Z$是朋友，但$X$和$Z$不是朋友。如果满足这个条件，则将$X$和$Z$合并成一个集合，表示建立新的朋友关系。

最后，我们统计并查集中集合的数量，即为可以执行操作的最大次数。



### 100 分做法

一个 $s$ 个点的边双连通分量，最多可以连$$\binom{s}{2} = \frac{s*(s-1)}{2}$$ 条边，对于题目给出的森林，用并查集维护连通块，连接给定的每组（$$a$$，$$b$$），合并（$$a$$，$$b$$）所在的两个连通块，同时统计每个连通块的边数，最大边数-现有边数=当前可以连的边数。

```c++
#include <bits/stdc++.h>
#include <vector>
#define coy cout<<"Yes"<<endl
#define con cout<<"No"<<endl
#define ll long long
#define ull unsigned long long int
#define forn(i,a,n) for(i=a;i<n;i++)
#include<iterator>
#define prec(ans) cout <<fixed<<setprecision(9)<< ans<<"\n"
#include <map>
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()


using namespace std;
//{-1,1},{-1,-1},{1,-1},{1,1},,{-1,0},{0,-1}
//ll mod=1e9+7;//998244353;
ll inf = 8e18;
const int N = 4e6 + 10;
ll mod = 1e9 + 7;

ll faspow(ll n, ll p) {
	if (p == 0)
		return 1;
	ll ret = faspow(n, p / 2) % mod;
	if (p % 2)
		return (((ret * ret) % mod) * n) % mod;
	else
		return  ((ret * ret) % mod);
}
ll modinv(ll n) {
	return faspow(n, mod - 2);
}
//{-1,1},{-1,-1},{1,-1},{1,1},
ll par[N], sz[N];
ll ro(ll u) {
	if (u == par[u])
		return u;
	return par[u] = ro(par[u]);
}
bool unite(ll u, ll v) {

	u = ro(u), v = ro(v);
	if (u == v)
		return false;
	if (sz[u] < sz[v])
		swap(u, v);
	sz[u] += sz[v];
	par[v] = u;
	return true;
}
int main() {
	freopen("sns.in", "r", stdin);
	freopen("sns.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t, k, T = 1, n, m, i, j;
	cin >> n >> m;
	forn(i, 1, n + 1)
	par[i] = i, sz[i] = 1;
	ll a, b;
	forn(i, 0, m) {
		cin >> a >> b;
		unite(a, b);
	}
	ll ans = -m;
	forn(i, 1, n + 1) {
		if (par[i] == i)
			ans += sz[i] * (sz[i] - 1) / 2;
	}
	cout << ans << endl;


	return 0;

//111111111111111
//OEIS
	/*5
	5 2 1 4 3
	*/
}
```

## 城市道路 (countpath.cpp)

### 20分题解

由于城市数很少，而数字很少，那么道路数量也就不会很多，所以可以直接用 DFS 来进行搜索。

### 50分题解

动态规划。设 $dp(i)$ 表示当前从城市 $1$ 到达城市 $i$ 的路径数量，那么最后的答案也就是 $dp(N)$。转移方程就从前面某一个城市 $j$ 直接到达城市 $i$，走法就是 $j \to i$ 的边数，转移方程如下：

$$
dp(i) = \sum\limits_{j=1}^{i-1} dp(j) \times F(A_i \& A_j)
$$

初值是 $dp(1) = 1$。时间复杂度为 $O(n^2 \log A_i)$。

### 100分题解


上述转移方程可以优化，主要集中于后面的 $F(A_i \& A_j)$，将其拆开为 $\sum_{k=0}^{30} [ (A_i \& A_j)_k == 1 ]$。其中 $[ \cdot ]$ 是 Iverson 括号，里面是一个表达式，当表达式为 True 时值为 $1$，否则为 $0$。这个和式等同于下面的代码：

```cpp
int ret = 0;
for (int k = 0; k <= 30; k++)
    if (((a[i] & a[j]) >> k) & 1)
        ret++;
return ret;
```

而条件 $(A_i \& A_j)_k == 1$ 又可以拆成 $(A_i)_k == 1 \text{ AND } (A_j)_k == 1$，也就是 $A_i$ 
与 $A_j$ 的第 $k$ 位都必须为 $1$。

那么转移方程就可以改写为：

$$
\begin{aligned}
dp(i) &= \sum\limits_{j=1}^{i-1} dp(j) \sum_{k=0}^{30} [ (A_i \& A_j)_k == 1 ]
\\
&= \sum\limits_{j=1}^{i-1} dp(j) \sum_{k=0}^{30} [(A_i)_k == 1 \text{ AND } (A_j)_k == 1]
\\
&= \sum\limits_{j=1}^{i-1} dp(j) \sum_{k=0}^{30} [(A_i)_k == 1]\cdot [(A_j)_k == 1]
\end{aligned}
$$

两个和式枚举的变量互不影响，所以可以交换两个和式的位置：

$$
dp(i) = \sum\limits_{k=0}^{30}[(A_i)_k==1]\sum\limits_{j=1}^{i-1}dp(j) \cdot [(A_j)_k == 1]
$$

观察右边的 $\sum\limits_{j=1}^{i-1}dp(j) \cdot [(A_j)_k == 1]$，实际上就是一个前缀和。这个前缀和针对每一个二进制位来维护，维护的是前面 $i-1$ 个城市中 $A_j$ 的第 $k$ 位为 $1$ 的所有 $dp(j)$ 之和。这个维护可以一边转移一边维护。

其实，上述做法的描述比较数学。形象一点的话，实际上就是考虑每一个二进制位对 $dp(i)$ 的 “贡献”。针对这种二进制的题目，一个比较常见的思路就是拆位，将每一个二进制位单独考虑。比如在本题中，每一个二进制位对应的就是一张没有重复边的图，那么转移也就比较简单，之后再向多个二进制位来考虑。本题中，不同二进制位之间其实是没有影响的，也就可以各个二进制位单独计算，然后再加起来即可。

时间复杂度：$O(n \log A_i) = O(30 n)$。




------

### Code

```cpp
#include <bits/stdc++.h>
using namespace std;
//using ll = long long;
#define ll  long long 
const int mod = 998244353;

int add(int a, int b) { return (a + b) >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return (a - b) < 0 ? a - b + mod : a - b; }
int mul(long long a, long long b) { return add(a * b % mod, mod); }

const int N = 2e5 + 50;

int n, a[N];
int s[31][N];
int dp[N];

void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int b = 0; b < 30; b++)
        for (int i = 0; i <= n + 5; i++)
            s[b][i] = 0, dp[i] = 0;

    dp[1] = 1;
    for (int b = 0; b < 30; b++)
        s[b][1] = mul(dp[1], ((a[1] >> b) & 1));

    for (int i = 2; i <= n; i++)
    {
        for (int b = 0; b < 30; b++)
        {
            int t = ((a[i] >> b) & 1);
            dp[i] = add(dp[i], mul(t, s[b][i - 1]));
        }
        for (int b = 0; b < 30; b++)
        {
            int t = ((a[i] >> b) & 1);
            s[b][i] = add(s[b][i - 1], dp[i] * t);
        }
    }
    int ans = dp[n];
    printf("%d\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}
```