CF840C On the Bench

发布于 2021-02-20 | 分类于容斥原理、计数 dp | 6分钟 | 1212字数

Description

给定长度为 $n$ 的序列 $\{a\}$ ，求 $\{a\}$ 有多少种排列，满足任意相邻两个数的乘积不是完全平方数。
答案对 $10^9+7$ 取模。
$n\leq 300$

阅读全文 »

CF961G Partitions

发布于 2021-02-19 | 分类于斯特林数及反演、思维 | 6分钟 | 1043字数

Description

有 $n$ 个物品，每个物品有一个权值 $w_i$ 。
现在你需要把这 $n$ 个物品划分成 $k$ 个非空集合。
定义在一个划分下物品的价值为权值和所在集合大小的乘积，一个划分的价值为所有物品的价值之和。

阅读全文 »

[CQOI2014] 数三角形

发布于 2021-02-19 | 2分钟 | 390字数

Description

给定一个 $n\times m$ 的网格，计算三个点都在格点上的三角形共有多少个。三角形的三点不能共线。
$n,m\leq 10^3$

Solution

阅读全文 »

CF917D Stranger Trees

发布于 2021-02-06 | 分类于 Prufer 序列、矩阵树定理、树形 dp | 8分钟 | 1576字数

Description

给定一棵有 $n$ 个节点的树。求对于每个 $k\in[0,n-1]$ ，有多少棵由这 $n$ 个点之间的边构造成的树，与给定的树恰好有 $k$ 条边重复。答案对 $10^9+7$ 取模。
$n\leq 100$

Solution

阅读全文 »

CF1285F Classical

发布于 2021-02-03 | 分类于反演相关 | 4分钟 | 672字数

Description

给定 $n$ 个数 $a_1,\cdots, a_n$ ，求两两 $\text{lcm}$ 的最大值。
$1\leq n,a_i\leq 10^5$

Solution

阅读全文 »

[JSOI2015] 骗我呢

发布于 2021-02-03 | 分类于容斥原理 | 8分钟 | 1606字数

Description

题面挺长的所以挂个链接

Solution

首先观察一下题面：它的值域不大。

阅读全文 »

UOJ499 喂鸽子

发布于 2021-02-01 | 分类于反演相关 | 8分钟 | 1425字数

Description

题面挺长挂个链接

Solution

「所有的鸽子都饱了」本质就是求每个鸽子第一次饱的时刻的最大值嘛，由于第一次本应是「最小」的含义，所以最值反演一手。

阅读全文 »

Luogu5221 Product

发布于 2021-01-31 | 分类于数论函数相关、反演相关 | 4分钟 | 754字数

Description

给定 $n$ ，求下式的值

\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)}

阅读全文 »

联合省选2020 作业题

发布于 2021-01-29 | 分类于矩阵树定理、数论函数相关 | 7分钟 | 1277字数

Description

题面挺长的所以挂链接

Solution

听说这是两个经典 trick 的结合，mark 一下。

阅读全文 »

CF1139D Steps to One

发布于 2021-01-28 | 分类于反演相关 | 4分钟 | 609字数

Description

给一个数列，每次随机从 $[1,m]$ 中选择一个数添加到数列末尾，直至数列的 $\gcd =1$ 时停止。求期望长度。
$1\leq m\leq 10^5$

Solution

阅读全文 »