ffacs 的博客
  文章分类
算法 15 solution 7 icpc 7 python笔记 3 笔记 12 Golang笔记 13
NOI2016 循环之美 NOI2016 循环之美
Solution 设分子为 \(x\) 分母为 \(y\) ,\((x,y)=1\)，循环节长度为 \(l\) ，那么有 \(xk^l \equiv x \models y \leftrightarrow k^l \equiv 1 \mod
2021-04-09 solution icpc
莫比乌斯反演 杜教筛
Luogu4491 [HAOI2018]染色 Luogu4491 [HAOI2018]染色
Description 为了报答小 C 的苹果, 小 G 打算送给热爱美术的小 C 一块画布, 这块画布可 以抽象为一个长度为 \(N\) 的序列, 每个位置都可以被染成 \(M\) 种颜色中的某一种. 然而小 C 只关心序列的 \(N\)
2021-03-31 solution icpc
多项式 生成函数 概率 容斥 二项式反演
Luogu3175 [HAOI2015]按位或 Luogu3175 [HAOI2015]按位或
Description 刚开始你有一个数字 \(0\) ，每一秒钟你会随机选择一个 \([0,2^n-1]\) 的数字，与你手上的数字进行或（C++, C 的 |， Pascal 的 or）操作。选择数字 \(i\) 的概率是 \(p_i\
2021-03-25 solution icpc
多项式 生成函数 概率 容斥
Luogu4451 [国家集训队]整数的lqp拆分 Luogu4451 [国家集训队]整数的lqp拆分
Description 求 \[ \begin{aligned} &F_0=0,F_1=1,F_n=F_{n-1}+F{n-2} \\ &\sum\prod_{i=1}^mF_{a_i}\models 1e9+7 \\ &a
2021-03-25 solution icpc
多项式 生成函数
Luogu1829Crash的数字表格 Luogu1829Crash的数字表格
Description \[ \sum_{i=1}^n\sum_{j=1}^m lcm(i,j), 1 \leq n,m \leq 10^7 \] Solution 假设 \(n\leq m\) \[ \begin{aligned} \su
2021-02-20 solution icpc
莫比乌斯反演
Luogu4449 于神之怒加强版 Luogu4449 于神之怒加强版
Description 给定 \(n,m,k\) ，计算 \[ \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k \] 对 \(10^9+7\) 取模后的结果，其中 \(1 \leq T \le 2\times 10^
2021-02-20 solution icpc
莫比乌斯反演
SDOI2017 数字表格 SDOI2017 数字表格
Description Doris 刚刚学习了 fibonacci 数列，用 \(f[i]\) 表示数列的第 \(i\) 项，那么： \[ \begin{aligned} &f[0]=0 \\ &f[1]=1 \\ &
2021-01-15 solution icpc
莫比乌斯反演