EagleBear2002 的博客

多项式乘法

问题背景

给定两个多项式 $A(x)$ 和 $B(x)$：

我们需要计算它们的乘积 $C(x)=A(x)\cdot B(x)$。

题目背景

一个简单的问题，什么是递推？

题目描述

定义一个数列 $\{a_0\dots a_{n-1}\}$ 的递推式为满足下式的序列 $\text{setr\_0dots r\_m}}$：

题目描述

小 A 是一个名副其实的狂热的回合制游戏玩家。在获得了许多回合制游戏的世界级奖项之后，小 A 有一天突然想起了他小时候在江南玩过的一个回合制游戏。

游戏的规则是这样的，首先给定一个数 $F$，然后游戏系统会产生 $T$ 组游戏。每一组游戏包含 $N$ 堆石子，小 A 和他的对手轮流操作。每次操作时，操作者先选定一个不小于 $2$ 的正整数 $M$（$M$ 是操作者自行选定的，而且每次操作时可不一样），然后将任意一堆数量不小于 $F$ 的石子分成 $M$ 堆，并且满足这 $M$ 堆石子中石子数最多的一堆至多比石子数最少的一堆多 $1$（即分的尽量平均，事实上按照这样的分石子万法，选定 $M$ 和一堆石子后，它分出来的状态是固定的）。当一个玩家不能操作的时候，也就是当每一堆石子的数量都严格小于 $F$ 时，他就输掉。补充：先手从 $N$ 堆石子中选择一堆数量不小于 $F$ 的石子分成 $M$ 堆后，此时共有 $N+M-1$ 堆石子，接下来小 A 从这 $N+M-1$ 堆石子中选择一堆数量不小于 $F$ 的石子，依此类推。

小 A 从小就是个有风度的男生，他邀请他的对手作为先手。小 A 现在想要知道，面对给定的一组游戏，而且他的对手也和他一样聪明绝顶的话，究竟谁能够获得胜利？

题目描述

一共 $n\times m$ 个硬币，摆成 $n\times m$ 的长方形。dongdong 和 xixi 玩一个游戏，每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方)，并且这个硬币是从反面向上翻成正面向上。dongdong 和 xixi 轮流操作。如果某一方无法操作，那么他(她)就输了。dongdong 先进行第一步操作，假设双方都采用最优策略。问 dongdong 是否有必胜策略。

输入格式

第一行一个数 $T$，表示他们一共玩 $T$ 局游戏。

题目描述

给定一个正整数 $m$，一个非负整数 $a$（$0\le a<m$），以及一个正整数序列 $A=(A_1,\dots ,A_N)$。

定义一个正整数集合 $X$，这个集合中的元素满足 $x>0$ 且 $x\equiv a(\mathrm{mod}m)$。

在这个游戏中，先手玩家太郎君和后手玩家次郎君轮流操作。游戏从太郎君开始进行，操作如下：

题目描述

小 E 与小 W 进行一项名为 E&D 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1\sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1\le k\le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

题目背景

一起长大的约定 那样清晰 拉过勾的我相信 说好要一起旅行 是你如今 唯一坚持的任性

——《蒲公英的约定》

题目描述

清和如在玩游戏。她们有 $n$ 丛蒲公英，每丛分别有 $s_i$ 朵。这些蒲公英有一个神奇的性质：有一个给定的常数 $\sigma \in (0,1)$，$x$ 朵蒲公英会分出 $\lfloor \sigma x\rfloor$ 朵为一组，剩下 $x-\lfloor \sigma x\rfloor$ 朵继续分组，直到分出的组没有蒲公英即 $\lfloor \sigma x\rfloor =0$ 为止。她们称这种现象为任性。现在她们的每丛蒲公英都有任性的现象。她们的游戏规则如下：从清开始，两人轮流进行旅行。一次旅行为选择一丛蒲公英并吹散这一丛的第一组中的若干朵蒲公英，至少要吹一朵，至多吹的朵数为第一组的朵数，即不能吹散除第一组外的蒲公英。当第一组为空时，其下一组成为第一组。若这一丛只剩下一组蒲公英，这一丛不能再被选定。每丛蒲公英都不能被选定时，游戏结束，当前轮到的人落败。她们想知道如果清第一次旅行时等概率选择其中一丛可吹散的蒲公英再等概率选择吹散的朵数后两人都按最优策略操作，那么清的胜率 $xmod20190816170251$ 的值将会是多少。

原题链接：P10501 Cutting Game - 洛谷

题目描述

Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $W\times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N+1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。

输入格式

博弈论的特点：没有什么套路，需要具体分析博弈性质。

P2197 【模板】Nim 游戏 - 洛谷：在许多地方曾经流行过这样一个小游戏：摆出三堆硬币，分别包含 3 枚、5 枚、7 枚。两人轮流行动，每次可以任选一堆，从中取走任意多枚硬币，可把一堆取光，但不能不取。取走最后一枚硬币者获得胜利。

这类游戏可以推广为更加一般的形式：

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手能否必胜。

题目描述

Bessie 有一行 $N$（$2\le N\le 300$）块瓷砖，依次具有丑陋度 $a_1,a_2,\dots ,a_N$（$1\le a_i\le {10}^6$）。其中 $K$（$0\le K\le min(N,6)$）块瓷砖卡住了；具体地，索引为 $x_1,\dots ,x_K$（$1\le x_1<x_2<\cdots <x_K\le N$）的瓷砖。

Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum _{i=1}^{N-1}max(a_i,a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。

求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。

输入格式