这个小 trick 有什么特别之处？
- 内容介绍
- 文章标签
- 相关推荐
本文共计652个文字，预计阅读时间需要3分钟。
通过两次平方变换，我们引入一个状态 \(S\)，每个状态 \(S\) 都有一个贡献 \(f(S)\)。所有状态 \(S\) 构成一个集合 \(U\)。接着，我们计算这个集合的方差 \(ans\)，公式为 \(\sum_{S \in U} f(S)^2\)。这样，我们就可以观察并选择 \(U\) 中任意的两个状态 \(S_1, S_2\) 来进一步分析。
trick平方变两次
一个状态 \(S\) 有一个贡献，所有状态 \(S\) 组成集合 \(U\) .
然后我们要统计下面这个东西
\[ans=\sum_{S\in U}f^2(S) \]然后我们就可以看作是选两个 \(U\) 里的 \(S_1, S_2\)，然后 \(S_1=S_2\) 的方案数 .
这样就把一个带平方的贡献问题转化成一个简单的选择了 .
让我们看一个实例：
NOI2009 管道取珠
两个字符串 \(S,T\) .
整一个仅含 \(1, 2\) 的序列 \(\{a\}\)，用以下步骤生成一个字符串 \(U\)：
- 扫描序列 \(\{a\}\) .
- 目前扫到了 \(x\)：
- 如果 \(x\) 是 \(1\)，从 \(S\) 的末尾拿一个字符放到 \(U\) 的开头，然后把 \(S\) 末尾那个字符删了 .
- 如果 \(x\) 是 \(2\)，从 \(T\) 的末尾拿一个字符放到 \(U\) 的开头，然后把 \(T\) 末尾那个字符删了 .
然后最后 \(S,T\) 都删没了得到的 \(U\) 就是生成出来的字符串 .
所有只有 \(n\) 个 \(1\)，\(m\) 个 \(2\) 的序列是合法的 .
令 \(f(X)\) 为序列 \(X\) 能被多少给合法序列生成 .
求
\[\sum_X f^2(X) \]对 \(1024523\) 取模 .
\(1\le n,m\le 500\) .
题解：
平方变两次，于是变成生成两次生成了相同的串的方案数 .
直接大力普及组 DP，令 \(dp_{i,j,k,l}\) 表示第一次 \(S\) 取 \(i\) 个，\(T\) 取 \(j\) 个；第一次 \(S\) 取 \(k\) 个，\(T\) 取 \(l\) 个的答案 .
然后轻松转移把 .
显然 \(i+j=k+l\)，于是可以滚掉一维度 .
于是这道题就被 \(O(n^2m)\) 解决了 .
一些类似的题目：
- BJOI2017 机动训练
- UOJ #667 提问系统（需要把原 Trick 推广到单项式）
- AGC013E Placing Squares
以下是博客签名，正文无关
本文共计652个文字，预计阅读时间需要3分钟。
通过两次平方变换，我们引入一个状态 \(S\)，每个状态 \(S\) 都有一个贡献 \(f(S)\)。所有状态 \(S\) 构成一个集合 \(U\)。接着，我们计算这个集合的方差 \(ans\)，公式为 \(\sum_{S \in U} f(S)^2\)。这样，我们就可以观察并选择 \(U\) 中任意的两个状态 \(S_1, S_2\) 来进一步分析。
trick平方变两次
一个状态 \(S\) 有一个贡献，所有状态 \(S\) 组成集合 \(U\) .
然后我们要统计下面这个东西
\[ans=\sum_{S\in U}f^2(S) \]然后我们就可以看作是选两个 \(U\) 里的 \(S_1, S_2\)，然后 \(S_1=S_2\) 的方案数 .
这样就把一个带平方的贡献问题转化成一个简单的选择了 .
让我们看一个实例：
NOI2009 管道取珠
两个字符串 \(S,T\) .
整一个仅含 \(1, 2\) 的序列 \(\{a\}\)，用以下步骤生成一个字符串 \(U\)：
- 扫描序列 \(\{a\}\) .
- 目前扫到了 \(x\)：
- 如果 \(x\) 是 \(1\)，从 \(S\) 的末尾拿一个字符放到 \(U\) 的开头，然后把 \(S\) 末尾那个字符删了 .
- 如果 \(x\) 是 \(2\)，从 \(T\) 的末尾拿一个字符放到 \(U\) 的开头，然后把 \(T\) 末尾那个字符删了 .
然后最后 \(S,T\) 都删没了得到的 \(U\) 就是生成出来的字符串 .
所有只有 \(n\) 个 \(1\)，\(m\) 个 \(2\) 的序列是合法的 .
令 \(f(X)\) 为序列 \(X\) 能被多少给合法序列生成 .
求
\[\sum_X f^2(X) \]对 \(1024523\) 取模 .
\(1\le n,m\le 500\) .
题解：
平方变两次，于是变成生成两次生成了相同的串的方案数 .
直接大力普及组 DP，令 \(dp_{i,j,k,l}\) 表示第一次 \(S\) 取 \(i\) 个，\(T\) 取 \(j\) 个；第一次 \(S\) 取 \(k\) 个，\(T\) 取 \(l\) 个的答案 .
然后轻松转移把 .
显然 \(i+j=k+l\)，于是可以滚掉一维度 .
于是这道题就被 \(O(n^2m)\) 解决了 .
一些类似的题目：
- BJOI2017 机动训练
- UOJ #667 提问系统（需要把原 Trick 推广到单项式）
- AGC013E Placing Squares
以下是博客签名，正文无关