【题解】「BZOJ2655」calc

一个序列 \(a_1,...,a_n\) 是合法的,当且仅当:

  • 长度为给定的 \(n\)
  • \(a_1,...,a_n\) 都是 \([1,A]\) 中的整数。
  • \(a_1,...,a_n\) 互不相等。

一个序列的值定义为它里面所有数的乘积,即 \(a_1\times...\times a_n\)

两个序列不同当且仅当他们任意一位不一样,求所有不同合法序列的值的和。

\(n\le 500\)
[========]

推荐这些文章:

【题解】人类智慧

\(\texttt{计蒜客T3203 }\text{人类智慧}\)
给定一张有 \(n\) 个点 \(m\) 条边的有向图,每个点上有点权,不妨认为 \(w_i\) 表示第 \(i\) 个点上的点权。还给了一个计数器以及一个正整数 \(T\),要求在任意时刻计数器的值都不能小于 \(0\) 或者大于 \(T\)。计数器初始时值为 \(0\),之后你可以在有向图上任意选择一条 路径(即边可以重复走),当每一次到达一个点 \(i\) 的时候,都可以进行以下操作之一:

不操作;
为计数器加上 \(w_i\);
为计数器减去 \(w_i\)。

起点是任意的,求可以让计数器达到的最大值。
(保证...

[题解] 密码 | 简单计数

同步发表于 Mina!

题目大意
对于满足以下要求的长度为 \(n\) 的序列进行计数:

序列的值域为 \([1,k]\);

对于序列的任意位置 \(p\in[1,n]\),可以找到至少一个 \(i\) 满足 \(p\in[i,i+k-1]\),且区间 \([i,i+k-1]\) 为一个 \(1\sim k\) 的排列。

\(n\le10^5,k\le100\)
解题思路
其实原本题意不是这样的,试图描述正式之后好像更难懂了。

密码是一个长度为 \(n\) 的序列。
密码由若干个 \(1\sim k\) 的排列拼接而成,且拼接时,不同排列可重叠。

于是不妨设 \(f_i\...

[国家集训队] 旅游 题解

题目大意
题目链接。
给定结点个数为 \(n\) 的有边权树,需要维护 \(m\) 次操作,分为如下 \(5\) 种:

修改某条边的边权。
对某条路径上的边的边权取为相反数。
查询路径上的边权和。
查询路径上边权的最大值。
查询路径上边权的最小值。

限制: \(1\le n, m\le 2\times 10^4\)。
解法
这是一道轻重链剖分边权转点权的模板题。
首先发现边权不易维护,但我们先前有用轻重链剖分维护点权的经验,所以考虑能否将边权移植为点权。
随后发现如果我们将每条边的边权赋给深度较深的那个点作为点权,每条边会唯一的赋到一个点上。
在这个前提上我们就可以通过轻重链剖分解决这个...

【题解】GCDEX 系列

Version 1
UVA11417 GCD
Description

多测,\(t\) 组数据。

给定整数 \(n\),求
\[\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)
\]

\(1\le t\le 100, 1\le n\le 501\)。

Solution
\(\Omicron(n^2)\) 暴力。
Code
略。
Version 2
UVA11424 GCD - Extreme (I)
SP3871 GCDEX - GCD Extreme
UVA11426 拿行李(极限版) GCD - Extreme (II)
Descri...

[题解] 序列(sequence)

题目大意
给定一个长度为 \(N\)​ 的非负整数序列 \(A_1,A_2, \ldots ,A_N\)​,和一个正整数 \(M\)​。序列 \(A\) ​满足 \(\forall 1 \le i \le N, A_i \in [0, 2^M)\)​。定义一个长度为 \(N\) ​的非负整数序列 \(B\) ​是合法的,当且仅当其满足如下三个条件:
(1)\(\forall 1 \le i \le N\)​, \(B_i \in [0,2^M)\)​;
(2)\(\forall 1\le i< N,(A_i\ \text{and}\ B_i )\ \le (A_{i+1}\ \te...

ARC135 简要题解

链接
D
首先,能操作的位置有 \((n - 1)(m - 1)\) 个,同时我们知道左上角 \((n - 1)(m - 1)\) 个格子可以取到任意值,因此这个问题的解域就是一个 \((n - 1)(m - 1)\) 个变元的线性空间,理论上可以找到 \(n + m - 1\) 条线性无关的恒等式。
仔细观察可以发现,每次操作同一行或同一列要么没有一个格子被操作,否则被操作的两个格子必定相邻也即在改行或该列的奇偶性相反,于是可以得到操作后的矩阵 \(b\) 与原矩阵 \(a\) 的关系:
\[\forall i, \sum\limits_{j = 1} ^ m (-1) ^ j b_{i,...

2022蓝桥杯A组题解

A
分类先横后竖或者先竖后横,手算即可。
B
公平博弈,情况数不多,sg定理爆搜即可。
C
答案是所有数和的平方
D
将序列全部异或x,转化为一段区间内原序列和新序列是否有相同元素,可以莫队,也可以维护前后最近一个相同的元素然后线段树。
E
考虑每次掉到树根之前所在位置,将其视为一个序列,相当于:每次在[1,n]随机一个数(随机到每个数的概率给定),第一次随机到n时终止,求序列和的期望。
枚举这个序列除开最后一项有i个数,那么:
\[E(序列和)=\Sigma_{i} P(序列长度==i)\times(前i-1的和的期望+n)\\
=\Sigma_{i} P(序列长度==i)\times (...

ABC234 G & H 题解

ABC234G Divide a Sequence
题面
题意:

给定一个长度为 \(n\) 的序列 \(A\),对于每一种把序列 \(A\) 分成 \(k\) 个子段(设为 \(B_1,B_2,\dots,B_n\))的方案(共有 \(2^{n-1}\) 种),定义其权值为 \(\prod\limits_{i=1}^k (\max(B_i)-\min(B_i))\),问所有划分权值的和 \(\mod998244353\) 的结果。
数据范围:\(1\le n\le3\times10^5\),\(1\le A_i\le10^9\)。

可以列出一个很显然的 DP:设 \(f_i\) 表示划...

CF1516D Cut 题解

一道套路题,做过同类型的题目应该能够直接看出做法。
这道题首先询问方式很像 DS 题的询问方式,但是实际上你会发现这道题做法是不能纯 DS 的,或者说这道题根本就不需要 DS。
发现如果乘积和 LCM 要相同的话需要满足这个区间内没有任意两个数最大公约数大于 1,而最大公约数可以归约到质因数上。
所以首先对每个数做一个质因数分解,然后考虑预处理出 \(r_i\) 表示第 \(i\) 个位置不断往右边扩展,能够扩展到的最右边的位置是什么,满足 \([i,r_i]\) 合法,且 \([i,r_i+1]\) 不合法或者是 \(r_i<n\)。
这个实际上开一个 \(cnt\) 数组双指针扫一...

NOI2022 密码箱 题解

题目链接:link
题意:
有一个数列\(a\),初始\(a_0=0,a_1=1\)。
并对数列定义一个函数\(f\):
\[f(a_0,a_1,\cdots,a_k)=\begin{cases}
a_0&if(k=0)\\
f(a_0,a_1,\cdots,a_{k-2},a_{k-1}+\frac1{a_k})&if(k>0)
\end{cases}
\]现在有两种操作:

\(E\):给数列最后一项加\(1\);

\(W\):若数列最后一项为\(1\),则给倒数第二项加\(1\);否则给数列的最后一项减\(1\),再在末尾补上\(2\)个\(1\)。
可以看...

文章标题:【题解】「BZOJ2655」calc
文章链接:https://www.dianjilingqu.com/4009.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>