SDOI

原题 \[\huge{\color{#ff0000}{\text{被XJK搏杀了，我tcl}}} \]我们先从\(n\)个数里选\(m\)个数钦定这些数满足\(a_i = i\)，因此原问题就等于让\(n-m\)个数的排列满足\(a_i \neq i\)的排列方案数 先说一个错误的做法：设\(dp_ ......

题目链接 description 给定一个质数 \(m\)，以及 \(n,x\) 和集合 \(S\)。从集合 \(S\) 中任意选数构成长度为 \(n\) 的数列（一个数可以选多次），求数列元素乘积模 \(m\) 等于 \(x\) 的数列的数量。模 \(1004535809\)。 \(3\leq m ......

# 【动态规划】【SDOI2017】序列计数 ### 题目描述 Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。 Alice 还希望，这 $n$ 个数中，至少有一个数是质数。 Alice 想知道，有多少个序列满足她的 ......

写了 $358$ 行，$11.94 \mathrm{KB}$，有这么几个地方写挂了： - 反猪决斗一定选主猪。 - 游戏结束判定是主猪死亡或全部反猪死亡。 - 决斗可能被反杀，之后不能再出牌。 点击查看代码 ```cpp #include using namespace std; int n,m; ......

# [P2486 [SDOI2011] 染色](https://www.luogu.com.cn/problem/P2486) 神仙树剖题。 ## 题意 给你一棵树，每个点都有颜色，支持下面两种操作： * 路径染色。 * 路径颜色段数量查询。 ## 树剖部分 我们看到树上问题，不好处理，所以想办法给 ......

[传送门](https://www.luogu.com.cn/problem/P2151) 简要题意：有$n$个人，$m$条无向边，走$e$条边，满足条件若第$i$条边为$u->v$则第$i+1$条边不能是$v->u$，问$s->t$的方案有多少个，取模45989。 因为要满足题目关于边的条件，所以 ......

[题目链接](https://ac.nowcoder.com/acm/problem/20313) # 题目 **题目描述** 作为体育委员，C君负责这次运动会仪仗队的训练。 仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断 ......

> 现在求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多，序列数对 10^9+7 取模。 # 输入 第一行一个数 T，表示有 T 组数据。 接 ......

> 你被要求设计一个计算器完成以下三项任务： 1.给定y、z、P，计算y^z^ mod P的值 2.给定y、z、P，计算满足xy≡z(mod P)的最小非负整数x； 3.给定y、z、P，计算满足y^x^≡z(mod P)的最小非负整数x。 # 输入 第一行包含两个正整数T，K 分别表示数据组数和询问 ......

### 题目描述 2020.4.29 数据更新。 打地鼠是这样的一个游戏：地面上有一些地鼠洞，地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时，用锤子砸其头部，砸到的地鼠越多分数也就越高。 游戏中的锤子每次只能打一只地鼠，如果多只地鼠同时探出头，玩家只能通过多次挥舞锤子的方 ......

# Description > [P3780 [SDOI2017] 苹果树](https://www.luogu.com.cn/problem/P3780) 给定一棵 $n$ 个点的树，每个点有若干个价值相同的苹果，儿子能摘至少一个仅当父亲被摘至少一个。 给定 $k$，设 $h$ 为你摘的苹果的最大 ......

题目链接：[【LuoguP3306】](https://www.luogu.com.cn/problem/P3306)。 ## 前置知识 OI-Wiki：[快速幂](https://oi-wiki.org//math/binary-exponentiation/)，[扩展欧几里得算法（exgcd）] ......

[P4607 [SDOI2018] 反回文串](https://www.luogu.com.cn/problem/P4607) 每次给出 $n,k,p$，求出长为 $n$ 的回文串以及其旋转变换的总数，且字符集大小为 $k$，答案对 $p$ 取模。 $T\le 10$，$n\le 10^{18}$， ......

[题目链接](https://www.luogu.com.cn/problem/P2149) 题意简述：求两条给定起点终点最短路的最长公共路径。 首先最长公共路径一定是两条最短路的公共最长链的部分。至少一定在两条最短路上。 考虑如何求出一条路径是否包含于一条最短路，只要路径 $x\rightarro ......

[Lnk](https://www.luogu.com.cn/problem/P4069) 首先树剖，然后变成在 $\text{dfn}$ 区间上插一个关于 $\text{dis}$ 的一次函数。这个很神奇，一般的李超树是，在 $x$ 轴区间上插入关于 $x$ 的一次函数。然而这里，$\text{d ......

# 洛谷 P3304 [SDOI2013] 直径 题解 [题目链接](https://www.luogu.com.cn/problem/P3304) ### 题目分析 第一部分好说，求直径，dfs或者DP都可以。 第二部分，有一个定理，就是所有直径中点重叠。 那么有两种情况 - 一种是中点在一个节点 ......

[传送门](https://www.luogu.com.cn/problem/P3704) 跟YY的gcd如出一辙，得到一个显然的柿子 $$\prod_{k} F_{k}^{z} $$ $$z= \sum _{d} \mu(d) \lfloor\frac{n}{kd} \rfloor \lfloor ......

[TOC] # 题目描述 [P4069 [SDOI2016] 游戏](https://www.luogu.com.cn/problem/P4069) > 一棵树，树上有 $n$ 个节点，最初每个节点上有$1$个数字：$123456789123456789$。有两种操作： $\centerdot$选择 ......

一、题目描述： 用 $f_i$ 表示斐波那契数列的第 $i$ 项，那么有： $ f_0=0,f_1=1;f_n=f_{n-1}+f_{n-2},n\ge2 $ 现在有一个 $n$ 行 $m$ 列的数字表格，第 $i$ 行第 $j$ 列的数字是 $f_{\gcd(i,j)}$ 。 求这个表格所有数的乘 ......

[题目链接](https://www.luogu.com.cn/problem/P1972) 对于这类问区间不同数的总数，显然是不能用线段树直接维护的，毕竟不符合区间区间可加性。 考虑对于一个右端点固定的询问，哪些数字实际上是有权值的。 比如区间 `1 3 3 2 3 1 2`，显然，实际上对于相同 ......

# [SDOI2010] 代码拍卖会 题解 ## 题目描述 一个 $n,n\le10^{18}$ 位数，仅由 $1\sim9$ 组成，后一位数字一定大于等于前一位数字。 求这些数中可以被 $m,m\le500$ 整除的有多少，对 $999911659$ 取模。 ## 解析 这个数一定形如 $1123 ......

# [P2458 保安站岗](https://www.luogu.com.cn/problem/P2458) **思路：** 树形DP 三个状态： - dp[i][0]：节点 i 位置放保安的最小花费 - dp[i][1]：节点 i 位置不放保安，但被子节点的保安看守 - dp[i][2]：节点 i ......

**[SDOI2009] Bill的挑战** [TOC] ## 题目描述 Sheng_bill 不仅有惊人的心算能力，还可以轻松地完成各种统计。在昨天的比赛中，你凭借优秀的程序与他打成了平局，这导致 Sheng_bill 极度的不满。于是他再次挑战你。这次你可不能输。 这次，比赛规则是这样的： 给出 ......

## 题意 现在你面前摆有 $1\ldots N$ 编号的 $N$ 只千足虫，你的任务是鉴定每只虫子所属的星球，但不允许亲自去数它们的足。 Charles 每次会在这 $N$ 只千足虫中选定若干只放入“昆虫点足机”（the Insect Feet Counter, IFC）中，“点足机”会自动统计出 ......

## 题意 求下列表达式的值 $$\large{g^{\sum_{d|n}{\binom{n}{d}}} \pmod{999911659} }$$ 其中，$n, d \leqslant 10^9.$ ## Solution 由欧拉定理可知， $$\large{ 原式 = g^{\sum_{d|n}{ ......

>tarjan 多测的时候 dfn 数组要清空！！！ >树剖多测的时候 son 数组要清空！！！ > 点双 tarjan 时可用 vector 建边，边双时用 vector 需要无重边 本题直接建圆方树，然后答案就是关键点构成的虚树上非关键原点个数。 ### 代码 ```cpp #include u ......

[题目链接](https://ac.nowcoder.com/acm/problem/20573) # 题目 **题目描述** 给定一棵有n个节点的无根树和m个操作，操作有2类： 1、将节点a到节点b路径上所有点都染成颜色c； 2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）， ......

# [SDOI2014]数表 ## 题目描述 有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。 $1\le n, ......

## 题面 一个由自然数组成的数列按下式定义： 对于 $i \le k$：$a_{i}= b_{i}$。 对于 $i > k$：$\displaystyle a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}$。 其中 $b_{1\dots k}$ 和 $c_{1 ......

# [SDOI2016]排列计数 ## 题目描述 求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。 答案对 $10^9 + 7$ 取模。 ## 输入格式 **本题单测试点内有多组数据**。 输入的第一行是一个整数 $T$，代表测试数据 ......