EagleBear2002 的博客

题目描述

对 $n$ 个点有标号的有向无环图进行计数，要求：弱连通图（所有的有向边替换为无向边后的图为连通图）。输出答案对 $998244353$ 取模的结果。

输入格式

一个整数 $T$。

输出格式

题目描述

到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影。最后大家在一个偏僻的小胡同里找到了一家电影院，但这家电影院分配座位的方式很特殊，具体方式如下：

电影院的座位共有 $K$ 个，并被标号为 $1 \sim K$。每个人买完票后会被随机指定一个座位，具体来说是从 $1 \sim K$ 中等概率随机选取一个正整数，设其为 $L$。

如果编号 $L$ 的座位是空位，则这个座位就分配给此人，否则将 $L$ 加一，继续前面的步骤；如果不存在编号 $L$ 的座位，则该人只能站着看电影，即所谓的站票。

小白班上共有 $N$ 人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。

题目描述

首先我们回忆一下经典难题过河卒问题：

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向上、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点，因此称之为「马拦过河卒」。

棋盘用坐标表示，$A$ 点 $(1,1)$ 、$B$ 点 $(N,M)$ ，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

请注意，上述背景内容与本题无关！

Kiana 喜欢玩象棋，尤其是喜欢用象棋玩过河卒的游戏。在传统的过河卒问题中，Kiana 需要控制一个卒从起点走到终点，在路中避开一个对方的马的攻击，然后假装不会算并询问你从起点到终点的路径总数。

在今天的过河卒二游戏中，Kiana 还是控制一个卒在一个 $N\times M$ 的棋盘上移动，初始时卒位于左下方坐标为 $(1,1)$ 位置，但为了增加难度，Kiana 对游戏规则做出了一些修改。传统的过河卒每步只能向上或向右移动 $1$ 格，Kiana 规定自己的过河卒二还可以在一步中向右上方移动 $1$ 格，即如果当前卒位于坐标 $(x,y)$ 处，则下一步可以走到 $(x+1,y)$ 、$(x,y+1)$ 或 $(x+1,y+1)$ 中的任意一格里面去，同时 Kiana 认为，如果两种移动方案在某一步时卒移动的方向（右、上或右上）不同，则两种方案就是不同的，例如从 $(1,1)$ 先走到 $(1,2)$ 再走到 $(2,2)$ 、从 $(1,1)$ 先走到 $(2,1)$ 再走到 $(2,2)$ 和从 $(1,1)$ 直接走到 $(2,2)$ 是三种不同的移动方案。

其次，过河卒二的终点不再是一个特定的位置，Kiana 规定卒可以从棋盘的上方或右方走出棋盘，此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同，例如若过河卒位于 $(1,M)$ 处，则下一步它可以向右或者向右上用两种方式走出棋盘，若过河卒位于 $(N,M)$ 处，则下一步它可以向上、向右或者向右上用三种方式走出棋盘，以不同的方式走出棋盘仍然被算作是不同的移动方案。

题目背景

终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。

题目描述

为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。

题目背景

这个三角图真好看。。

这个是 ${\rm 4}$ 阶三角图。。

题目描述

题目描述

众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。

他将声音分成 $n$ 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 $1$ 到 $n$ 个音阶构成的和声，即从 $n$ 个音阶中挑选若干个音阶同时演奏出来。

为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。

现在的问题是：小余想知道包含 $m$ 个片段的音乐一共有多少种。

题目描述

牛牛有一块蛋糕，他想把蛋糕分给小朋友们。蛋糕一开始是圆形的，牛牛会在圆周上选择 $n$ 个不重合的点，将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。

现在，牛牛想知道，蛋糕最多会被分成多少块，请你告诉他答案。

输入格式

输入包含至多 $20$ 行，每行一个整数 $n$，含义见「题目描述」。保证 $0\le n \le 64$。

题目描述

求 $n$ 个点的无向完全图删去一条边之后圈的个数，答案模 $998244353$。

注：圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径。

输入格式

第一行一个整数 $T$，表示数据组数。

题目描述

聪明的 Cirno 开始学习计算，于是她很开心的算出了从 $1$ 一直加到 $n$。

得到了一个 $n$ 项的数列 : $\set{ a_n = 1 + 2 + 3 + 4 + ... + n}$。

为了验证自己算是否算错，她需要以某种规律从数列里取出两个元素 $v_1, v_2$（元素可以相同），并等概率的选出整数 $a \in [ 1,v_1 ]$，$b \in [ 1,v_2 ]$ 判断哪个比较大。

所以她需要你来计算 $a>b$ 的概率。

题目描述

Zeit und Raum trennen dich und mich.

时空将你我分开。

B 君在玩一个游戏，这个游戏由 $n$ 个灯和 $n$ 个开关组成，给定这 $n$ 个灯的初始状态，下标为从 $1$ 到 $n$ 的正整数。

每个灯有两个状态亮和灭，我们用 $1$ 来表示这个灯是亮的，用 $0$ 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。

但是当操作第 $i$ 个开关时，所有编号为 $i$ 的约数（包括 $1$ 和 $i$）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。