OI经验
dztlb
·
·
个人记录
3 月 8 日讲义（计数）
Section 1
处理 k 次方和的一类问题（一般来说 k\le 100，甚至 k\in \{2,3,4\}）。
假如说有个计数问题，令 S 为所有合法方案构成的集合。每个方案 x\in S 有一个价值 val(x)，我想计算
\sum_{x\in S} val(x)^k.
标准手段
- 组合意义（一般来说，你可以把 val(x)^k 理解成 ”从 val(x) 个元素中，可以重复地选择 k 个的方案数）。
- 拆括号（假如说 val(x) = x_1 + x_2 + ... + x_t，那么 val(x)^2 = (x_1+x_2+...+x_t)^2 = \sum_{i,j} x_i x_j）。
- 二项式定理
- 斯特林数。
例 1 OSU！
你要随机生成一个长度为 n 的 01 序列，第 i 个位置以 pi 的概率为 1，以 1-p_i 的概率为 0. 你最后得到的序列的价值定义为所以 "1的连续段" 的长度的立方和。
（比如说 0 0 1 1 1 0 1 0 1 1 0 0 的价值 3^3+1^3+2^3）。
求你最后生成的序列的价值的期望。
解法
令 X_i 表示考虑01序列的前 i 个元素，后缀的 1 连续段的长度。
如果说 i+1 是 0：产生 X_i^3 的贡献。否则的话它转移到 X_{i+1}，E[(X_{i+1})^3] = p_{i+1} E[(X_i+1)^3].
例 2
（原创？）给出 n 个整数 a_1,\dots, a_n 排成 1 列。我们在每相邻的两个数之间随机插入 AND / OR / XOR，得到一个式子，(从左到右）计算这个式子可以得到一个值。问最终得到的值的平方的期望。
解法
所有运算都是按位运算。
把一个数按照二进制写开 v = v_{31}\cdot2^{31} + v_{30} \cdot 2^{30} + ... + v_1 \cdot 2 + v_0。它的平方 v^2 = (... + ... + ...)^2，我把平方拆开，就可以把计算归约到计算”任意两个位的乘积期望“。
当我们只关注某两个位的时候，可以做DP：$f[k][0/1][0/1]$ 表示处理了前 k 个数，我关注的两个位分别是 blabla 的概率。
复杂度：$32^2 \cdot n$。
#### 管道取珠
跳过。
#### 例
给定一个 $n$ 个点的无权树。给定 $m\le 100$，求 $\sum_{i,j} dis(i,j)^m$。$n\le 10^5$。
##### 解法
DP：$g[x][k]$：表示以 $x$ 为根的子树里所有点到 $x$ 的距离的 $k$ 次方和。 $O(m^2 n)$。
两种点对：
* 祖先 - 后代
* 其他情况。
优化：$f[x][k] = \sum_{y:x子树内} dis(y,x)^{k\downarrow}$.
$$
n^{k\downarrow} = n(n-1)(n-2)\dots (n-k+1).
$$
组合解释：从 $y$ 到 $x$ 这一条路中有 $dis(y,x)$ 这么多条边，我在其中（有顺序的）选 $k$ 条不同的边的方案数。
转移：$\sum_{d_2} (d_2+1)^{k\downarrow} = \big((d_2-k+1)+(k)\big)(d_2)\dots (d_2-k+2) = f(y,k) + f(y,k-1)\cdot k$.
计算答案？
* 想法一：在每个点转化回通常幂的和。（转化会花费 $m^2$ 的时间，$O(m^2 n)$)
* 想法二：斯特林数。
* $$
d^m = \sum_{i=0}^m S_2(m,i) \cdot d^{i\downarrow} \\
d^m = \sum_{i=0}^m S_2(m,i) {d\choose i} \cdot i!
$$
* $S_2(m,i)$ 表示把 $m$ 个元素分成 $i$ 个非空集合的方案数。
* 组合理解：$d^m$ 是把 $m$ 个元素放进 $d$ 个框里的方案数。枚举 $i$ 个框非空。先把 $m$ 个元素分成 $i$ 组，再从 $d$ 个框里选出 $i$ 个来放。
* （一种理解：考虑 $m=2$ 的情形：$d^2$ 可以表示一个有 $d$ 个同学的班级，要选出一个班长和一个学习委员的方案数。如果班长和学委不是同一个人：$d^{2\downarrow}$；如果是同一个人的话：$d^{1\downarrow}$。$m=3$ 的情形，$d^3$ 可以表示要选一个班长、学委和体委的方案数。我可以做分类讨论：班长学委体委 互不相同 / 班长学委是同一个人 / 学委体委同一个人 / 班长体委是同一个人 / 三个都是同一个人）对于一般的 $m$，我不想做分类讨论：用斯特林数就给出了一个通用的公式。
回到原题，我们可以得到：$\sum_{i,j} dis(i,j)^m = \sum_{k=0}^m S_2(m,k) \cdot \sum_{i,j}dis(i,j)^{k\downarrow}$.
* 换根DP：在 $O(mn)$ 的时间里，算出以每个点 $x$ 为根的时候，$f(x, i) = \sum_{y}dis(x,y)^{i\downarrow}$。
#### 习题
> 给定 $n, m$，求所有 $n$ 个点的带标号无向图的连通块个数的 $m$ 次方和。$n\le 50000, m\le 20$，结果对 $998244353$ 取模。
### Section 2 杂题
#### CoinChange：
> 你有面值为 $10^k, k\in \{0,1,2,..., \infty\}$ 以及 $5\cdot 10^k, k\in \{0,1,2,\dots, \infty\}$ 的钞票。每种钞票你都有无限张。
>
> 问有多少种方案能凑出 $M$ 元。$M\le 10^{18}$。
##### 解法
价值为 $v$ 的物品对应的生成函数 $\frac{1}{1-x^v}=1+x^v+x^{2v}+\dots $.
令 $S = \{10^k, 5\cdot 10^k\}$，那么我想计算：
$$
[x^M]\left( \prod_{v\in S} \frac{1}{1-x^v}\right)
$$
我们把面值从小到大排序，假如说 $1=v_1 < v_2 < v_3 < \dots < v_T \le M$。
我写一个naiveDP：$f(i, w)$ 表示只使用前 $i$ 个面值，凑出 $w$ 元的方案数。
首先：
* $f(1, w) \equiv 1$。
* 当我对 $v_1$ 做完决策之后，我需要保证 $M\bmod v_2 = w \bmod v_2$.
* 如果我想凑出 23 元，这个余数 ”3“ 我只能用 1 元来凑。
* 换句话说，我只关心 $w \bmod v_2 = M\bmod v_2$ 的那些 $w$ 的 DP 值。
* 令 $r = M\bmod v_2$，我们定义一个变换：$g(1, w) = f(1, w \cdot v_2 + r)$ 。
* 假如说 $f(1,w)$ 是一个关于 $w$ 的多项式 $P(w)$，那么 $g(1,w) = P(wv_2 + r)$ 也是一个关于 $w$ 的多项式。
* 之后的运算里，我们就用 $g(1, w)$ 去做 DP，我们可以把 $v_2,\dots, v_T, (M-r)$ 都除以 $v_2$。
* $f(1, x) => f(2, x + t\cdot v_2)
- 对应于 g(1, x) => g(2, x+t)。
- 从 g(1, \cdot) 转移到 g(2, \cdot) 需要枚举用了多少 v_2：
-
- 如果 g(1, w) 它是一个 k 次多项式，前缀和之后就得到了 (k+1) 次多项式。
- 之后用同样的trick：对 v_2 做完决策之后，需要保证 M\bmod v_3 = w \bmod v_3。
- 定义一个变换：h(2, w) = g(2, w\cdot v_3 + r_2) （r_2 = M\bmod v_3）。
- 继续用 h 做DP。
- 重复这个过程，直到每一种面值都处理过，你得到一个最终的多项式，把最终的M代入求值。
回顾：
- 初始 f(1, \cdot ) \equiv 1 是一个 0 次多项式。
- 每次：我先把当前 DP 数组里 mod v_{i+1} 相同的一列值取出来。对它们做一个前缀和，得到下一轮的 DP 数组。
如果有 K 个不同的面值的话，时间复杂度是 O(K^3) 或者 O(K^2)。
基于斯特林数的容斥
异或图
给定 m 张无向图。每个图的大小都是 n=10。 m\le 64。
定义两张图 G_1,G_2 的异或为 G_1\oplus G_2，一条边在 G_1\oplus G_2 出现，当且仅当它在G_1, G_2 两个图里的恰好一张出现。
问多少个不同的子集，使得子集的异或图联通。
解法
容斥：首先不考虑任何限制，有 2^m 张图。
对于不连通的图，我们枚举它的一个划分 [n] = S\sqcup T，我们要求 S、T 之间没有边，计算出这种情形下的子集个数（高斯消元）（每条跨越 S、T 的边给出一个线性限制，联立一个方程组。计算这个方程组的秩为 r，那么方案数为 2^{m-r}）。从 2^m 里把它们减掉。
这样的问题在于可能会多减：如果一个图里实际上有三个连通块，那么在上述过程里会被减掉 3 次。我们把它补回来：我们枚举划分 [n] = S\sqcup T\sqcup R，要求 S,T,R 两两之间没有边，计算出方案数 w，我们在最终答案里加上 2w。
上述的问题在于可能会多加：如果一个图有 4 个连通块，它目前的贡献是：1 - 7 + 6\cdot 2 = +6. 我们把它再减掉：枚举 [n] = S\sqcup T\sqcup R\sqcup Q，要求两两没有边。计算出方案数 w，在答案里减掉 6w。
一般地，我们枚举把 [n] 个点划分成 k 个非空连通块，要求连通块之间没有边，计算出方案数 w，在最终答案里加上 (k-1)!\cdot (-1)^{k-1}。
正确性：假如说一个图实际有 c 个连通块，它在这个计算过程中的总贡献是：
\sum_{k=1}^c S_2(c, k) \cdot (-1)^{k-1} \cdot (k-1)! = [c = 1].
复杂度：O(bell(n) \cdot n^2\cdot m)，其中 bell(n) 表示把 n 个元素划分成若干个集合的方案数（它相当于一行第二类斯特林数的和）。
n 个点 m 条边的带标号简单无向连通图个数
##### 解法
标准做法：DP：$f(n, m)$ 表示 n 个点 m 条边的无向连通图个数。
转移：用所有的图，减掉不合法的。对于不合法的图，枚举 1 号点所在的连通块的情形。
$$
f(n, m) = {{n\choose 2} \choose m} - \sum_{i=1}^{n-1} \sum_{j=0}^m {n-1\choose i-1}\cdot f(i,j) \cdot {{n-i\choose 2}\choose m-j}.
$$
复杂度：$O(n^6)$：状态 $O(n^3)$，转移 $O(n^3)$。
用斯特林数容斥，希望设计一个状态数 $O(n^3)$，转移 $O(n)$ 的算法。
##### 容斥
Naive 想法：用所有的图，减去至少有两个连通块的。
$$
\binom{n\choose 2}{m} - \sum_{i=1}^{n-1} {n-1\choose i-1} {{i\choose 2}+{n-i\choose 2}\choose m}
$$
如果一个图里实际有 3 个连通块，它会在方案里计 -2 倍的贡献。我们加一个修正项：
$$
2\cdot \sum_{i_1+i_2+i_3 = n} (把n个点划分成i_1+i_2+i_3的方案) \cdot {{i_1\choose 2}+{i_2\choose 2}+{i_3\choose 2}\choose m}
$$
一般地，如果一个图里实际有 $k$ 个连通块，它会在之前的计算里计 $(k-1)!\cdot (-1)^{k}$ 的贡献，加一个修正项：
$$
(k-1)!\cdot (-1)^{k-1} \sum_{i_1+i_2+\dots+i_k = n} (划分的方案) \cdot {{i_1\choose 2}+...+{i_k\choose 2}\choose m}.
$$
我们现在考虑用一个DP来实现这个计算：
* 一个比较naive 的想法是，令 $g(k, n, t)$ 表示 "把 $n$ 个点划分成 $k$ 块，划分结束之后有 $m$ 个可以连边的点对" 的方案数。
* 转移：$g(k, n, m) = \sum_{i=1}^n {n-1\choose i-1} \cdot g(k-1, n-i, m - {i\choose 2})$.
* 答案：$ANS = \sum_{k=1}^n (k-1)!\cdot (-1)^{k-1} \cdot \sum_t g(k, n, t)\cdot {t\choose m}$。
* 复杂度：$g$ 的状态数 $O(n^4)$，转移 $O(n)$，答案统计 $O(n^3)$，总复杂度 $O(n^5)$。
**优化**. 我们希望优化掉 $g(k, n, m)$ 里面的 $k$ 这一维。考虑答案是怎么计算出来的：
$$
ANS = \sum_{t} {t\choose m} \cdot \sum_{k=1}^{n} (k-1)! (-1)^{k-1} g(k,n,t).
$$
考虑一个简单一点的问题：
$$
ANS = \sum_{t} {t\choose m} \cdot \sum_{k=1}^{n} g(k,n,t).
$$
* 在这个例子里，可以直接优化掉 $k$ 这一维。令 $g(n,t)$ 表示 n 个点划分成若干块，划分完之后有 t 个可以连边的点对。
考虑一个稍微难一点的问题：
$$
ANS = \sum_{t} {t\choose m} \cdot \sum_{k=1}^{n} (-1)^{k-1} g(k,n,t).
$$
* 令 $g(n,t)$ 表示 n 个点划分成若干块，划分完之后有 t 个可以连边的点对，根据块数的奇偶性产生 +1 / -1 的贡献。
* 每次加入一个新的块会翻转奇偶性，翻转符号就可以了。$g(n, m) = \mathrm{1}[m=={n\choose 2}] -\sum_{i=1}^n {n-1\choose i-1} \cdot g( n-i, m - {i\choose 2})$.
考虑一个更难一点的问题：
$$
ANS = \sum_{t} {t\choose m} \cdot \sum_{k=1}^{n} k!\cdot (-1)^{k-1} g(k,n,t).
$$
* 令 $g(n,t)$ 表示 n 个点划分成**有顺序的**若干块，划分完之后有 t 个可以连边的点对，根据块数的奇偶性产生 +1 / -1 的贡献。
* 修改一下 DP，不需要钦定一号点：$$g(n, m) = \mathrm{1}[m=={n\choose 2}] -\sum_{i=1}^n {n\choose i} \cdot g( n-i, m - {i\choose 2})$$.
考虑我们实际要算的值：
$$
ANS = \sum_{t} {t\choose m} \cdot \sum_{k=1}^{n} (k-1)!\cdot (-1)^{k-1} g(k,n,t).
$$
* 为了体现 $(k-1)!$，我们只让最后一次枚举是无序的。
* 令 $g(n,t)$ 表示 n 个点划分成**有顺序的**若干块，划分完之后有 t 个可以连边的点对，根据块数的奇偶性产生 +1 / -1 的贡献。
* $g(n, m) = \mathrm{1}[m=={n\choose 2}] -\sum_{i=1}^n {n\choose i} \cdot g( n-i, m - {i\choose 2})$.
* 我们定义 $h(n, t)$ 表示一个辅助数组。
* $h(n, m) = \mathrm{1}[m == {n\choose 2}] - \sum_{i=1}^{n} {n-1\choose i-1} \cdot g(n-i, m - {i\choose 2})$.
那么：
$$
ANS = \sum_{t} h(n, t)\cdot {t\choose m}.
$$
最后的复杂度就是 $O(n^4)$。
##### 应用
> 给定一个 $n$ 个点的图，初始为空。每次随机一个pair $(u, v) \in {[n]\choose 2}$，在 u 和 v 之间连一条边。重复这个过程直到图连通。
>
> 问期望多少次之后这个过程停止。 $n \le 100$。
##### 解法 1
假设在图连通之后，这个随机过程**并不会**停下来。
当图不连通的时候，我们执行一步过程需要花费 1 元钱；否则的话免费。我们把这个过程执行无穷多步，问我们期望的花费是多少。
考虑这个随机过程已经运行了一段时间。假如说现在图里有 $t$ 条本质不同的边。那么此时图连通的概率为 $f(n, t) / {{n\choose 2}\choose t}$。
如果图不连通的话，我们需要花钱来执行这个随机过程。每次随机，有 $\frac{t}{{n\choose 2}}$ 的概率随到一条已经有的边。期望下我需要花费 $\frac{{n\choose 2}}{{n\choose 2} - t}$ 元钱来连出下一条本质不同的边。所以期望下我在这个过程中的花费是 $\left( 1 - \frac{f(n, t)}{{{n\choose 2}\choose t}}\right) \cdot \frac{n\choose 2}{{n\choose 2} - t}$。
对 $t$ 求和得到：
$$
ANS = 1 + \sum_{t=1}^{{n\choose 2}} \left( 1 - \frac{f(n, t)}{{{n\choose 2}\choose t}}\right) \cdot \frac{n\choose 2}{{n\choose 2} - t}.
$$
##### 解法 2
$$
ANS = E[步数] = \sum_{i=0}^{\infty} \Pr[图在 i 步之后没有连通]
$$
考虑计算 $\Pr[图在 i 步之后没有连通]$：容斥。
枚举把 $n$ 个点划分成两份，要求不能存在跨越的边：$\sum_{i} {n-1\choose i-1}\left(\frac{{i\choose 2}+{n-i\choose 2}}{n\choose 2}\right)^i$.
这么算不对：如果有一次随机过程把图分成了 3 块，那这个过程在上面的式子里产生了 3 份贡献。枚举 3 划分，把这些贡献减掉。
。。。
### 比赛经验
赛前
赛时
考前半小时 写文操快读等必要东西，可以用压缩软件提前看题目名，节省时间
考试进行时 时间规划很重要。建立自己的反馈机制。（例：儒略日）
注意时效。恰烂分也香——暴力的重要性（快速拿分，提示正解）。
一些 历年省一线的例子。
合理舍弃程序的正确性：乱搞。（ NOIP T3 ）
赢在考试——通过签到题（开场读题好习惯，0.5h读题绝对不亏）。
赛后 ： 这还卷？！
### 学习经验
算法 流派招式
没有很难的算法。现在 CCF 已经有了考纲。但我觉得早在这之前，任何一个善于总结的人都能自己得出其中的结论：FFT 和生成函数是不考的；LCT 是不考的；计算几何几乎是不考的......。有趣的是，OI 模拟赛中经常出现这些知识点。我不喜欢这一现象，一方面它不能起到“模拟”的作用（准确反映出选手在正式比赛当中的水平），另一方面它会给选手的训练带来一些错误的引导。
算法是基础但不能过于强调。
身怀屠龙之术，不识龙为何物，直沦为暴力老哥。
（历年正解）一些常用算法的普遍出现 历年的DP。
思维 识破
基础的算法有其固有的套路，非常重要。很多基础算法的固有套路，在比赛里多次出现过。第一次遇到时不容易自己想到，看了题解往往让人直呼巧妙。当你在平时遇到一道题，是基础算法在某些条件下的巧妙使用，请一定要多加关注。例如：很多二维 DP 可以把第二维搬到线段树上；需要考虑序列上所有区间，可以分治，每次只解决跨过中点的区间；多次矩阵快速幂，可以通过预处理矩阵的 2k 次幂，转化成向量乘法......。
分析问题性质的能力很重要。很多题看起来很难，其实是通过巧妙的设计，隐藏了关键的性质。有时候选手一读完题会被看似复杂的问题震住，然后就停止思考了。此时特别需要选手静下心来，在纸上写写画画，认真分析题目性质，将复杂的、实际的问题，转化成简单的、本质的模型。有时候完成这些分析，解题就成功了一大半。
建立自己的知识框架（网络流的流传，NOIT1的树剖）。
出题人的角度。
做题提取本质。（讲相互联系的题）
最重要的能力（贯穿始终，算法代码积累一定程度都会）
（讲一点思维题）移球游戏，贪吃蛇
代码 忍杀
强大的代码能力和良好的代码习惯。（例5 冬令营血亏80pt）
首先特殊的语法，空间MLE，RE的敏感性，memset是否导致错误的时间复杂度，交互题，乃至传统题避免与std重名(nxt)。
不要过于依赖调试，甚至是输出调试，对自己代码持保留态度。
如何提升：虽然有题解，但还是建议对这自己代码硬调，代码能力就是在每次犯错、反馈的机制下练出来的，比赛爆炸不如平时头铁。
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1; char s;
while((s=getchar())<'0'||s>'9') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+(s^'0'),s=getchar();
return x*f;
}
const int N=3e5+5;
int T,n,m,q,rt,ans;
int gn(int i,int j){
if(i<1||i>n||j<1||j>m) return 0;
return (i-1)*m+j;
}
int head[N],tot;
struct node{
int to,nxt,w;
}e[N<<2];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
inline void add(int u,int v,int w){
if(!v||!u) return;
e[++tot].to=v,e[tot].nxt=head[u],head[u]=tot,e[tot].w=w;
e[++tot].to=u,e[tot].nxt=head[v],head[v]=tot,e[tot].w=w;
}
struct po{
int col,lv;
}p[N];
bool ok[N],fl[N],vis[N];
int que[N],top;
inline bool check(int u,int v){
if(!u||!v) return 0;
if(p[u].col!=p[v].col&&p[u].lv>=p[v].lv) return 1;
return 0;
}
void dfs(int u,int fap){
if(vis[u]) return;
vis[u]=1;
if(!fl[u]) ++ans,fl[u]=1,que[++top]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==0) continue;
if(e[i].w!=3||v==fap) continue;
if(ok[v]){
if(check(rt,v)) if(!fl[v])++ans,fl[v]=1,que[++top]=v;
}else if(!vis[v])dfs(v,u);
}
}
void dfs2(int u,int x,int y,int fap,int ty){
if(vis[u]) return;
vis[u]=1;
if(!fl[u]) ++ans,fl[u]=1,que[++top]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fap||e[i].w!=2) continue;
int tmp=gn(x+dx[ty],y+dy[ty]);
if(tmp!=v) continue;
if(ok[v]){
if(check(rt,v)) if(!fl[v]) ++ans,fl[v]=1,que[++top]=v;
}else dfs2(v,x+dx[ty],y+dy[ty],u,ty);
}
}
char s[N<<1];
int main(){
// freopen("chess.in","r",stdin);
// freopen("chess.out","w",stdout);
T=read();
while(T--){
memset(head,0,sizeof(head)),tot=0;
memset(ok,0,sizeof(ok));
memset(fl,0,sizeof(fl)); top=0,rt=0,ans=0;
n=read(),m=read(),q=read();
for(int i=1,ty;i<=n;++i){
scanf("%s",s+1);
for(int j=1;j<m;++j){
ty=s[j]-'0';
add(gn(i,j),gn(i,j+1),ty);
}
}
for(int i=1,ty;i<n;++i){
scanf("%s",s+1);
for(int j=1;j<=m;++j){
ty=s[j]-'0';
add(gn(i,j),gn(i+1,j),ty);
}
}
for(int i=1,col,lv,x,y;i<=q;++i){
ans=0;
for(int j=1;j<=top;++j) fl[que[j]]=0;
top=0;
col=read(),lv=read(),x=read(),y=read();
p[gn(x,y)].col=col,p[gn(x,y)].lv=lv;
ok[rt]=1;
rt=gn(x,y);
//处理直通道路
for(int j=head[rt];j;j=e[j].nxt){
int v=e[j].to;
if(e[j].w==2){
if(ok[v]){//有就不能走了
if(check(rt,v)) ++ans,fl[v]=1,que[++top]=v;
}
else for(int k=1;k<=4;++k){
int tmp=gn(x+dx[k],y+dy[k]);
if(tmp==v){
memset(vis,0,sizeof(vis));
vis[rt]=1;
dfs2(v,x+dx[k],y+dy[k],rt,k);
break;
}
}
}
}
//处理其他道路
for(int j=head[rt];j;j=e[j].nxt){
int v=e[j].to;
if(e[j].w==0||e[j].w==2) continue;
if(e[j].w==1){
if(!ok[v]) { if(!fl[v]) ++ans,fl[v]=1,que[++top]=v;}
else if(check(rt,v)) if(!fl[v]) ++ans,fl[v]=1,que[++top]=v;
}else{
if(ok[v]) { if(check(rt,v)&&!fl[v]) ++ans,fl[v]=1,que[++top]=v;}
else {
memset(vis,0,sizeof(vis));
vis[rt]=1;
dfs(v,rt);
} //只有互通道路才需要dfs
}
}
cout<<ans<<'\n';
}
}
return 0;
}
```