2022“杭电杯”中国大学生算法设计超级联赛(6)- 1011 Find different
2024-09-18 07:00:03
2022“杭电杯”中国大学生算法设计超级联赛(6)- 1011 Find different
比赛时队友开摆,还剩半个小时,怎么办??
当然是一起摆
Solution
看到这个题没多少时间了,没时间细想了,\(\text{DP}\)貌似不可行,一看这个东西就很置换群,火速上\(\text{Burnside}\)引理搞一波,虽然比赛结束也没推完就是了
题意就是问你有多少个本质不同的自然数序列\(a_1,a_2,...,a_n\),其中\(0 \le a_i \le m\),本质相同当且仅当能通过若干次全部模\(m\)意义下\(+1\)和整体循环左移得到。
考虑左移\(i\)位,全部加了\(j\),先考虑旋转,有经典结论,形成了\(\gcd(n,i)\)个循环置换,其中每个循环的长度为\(\frac{n}{\gcd(n,i)}\),然后我们对着这个\(\gcd(n,i)\)一顿操作,希望能够找到一个小环的不动点个数然后乘起来就行了。
自己画个图感受一下,可以发现一个小环的不动点个数有点复杂但比较简单,考虑最小的\(k\)使得\(kj \equiv 0\pmod m\),很容易发现
\[k=\frac{\operatorname{lcm}(m,j)}{j}=\frac{m}{\gcd(m,j)}
\]
\]
那么当且仅当\(\frac{m}{\gcd(m,j)} | \frac{n}{\gcd(n,i)}\)有贡献\(m^{\gcd(n,i)}\)
所以可以写出不动点总个数的式子
\[\begin{aligned}
& \sum_{i=1}^n \sum_{j = 1}^m [\frac{m}{\gcd(m,j)} | \frac{n}{\gcd(n,i)}] m ^ {\gcd(n,i)} \\
&= \sum_{i | n} m ^ i \varphi(\frac{n}{i}) \sum_{j | m} \varphi(\frac{m}{j}) [\frac{m}{j} | \frac{n}{i}]\\
&=\sum_{i | n} m^i \varphi(\frac{n}{i}) \sum_{j | \gcd(m,\frac{n}{i})}\varphi(j)\\
&=\sum_{i | n} m^i \varphi(\frac{n}{i}) \gcd(m,\frac{n}{i})
\end{aligned}
\]
& \sum_{i=1}^n \sum_{j = 1}^m [\frac{m}{\gcd(m,j)} | \frac{n}{\gcd(n,i)}] m ^ {\gcd(n,i)} \\
&= \sum_{i | n} m ^ i \varphi(\frac{n}{i}) \sum_{j | m} \varphi(\frac{m}{j}) [\frac{m}{j} | \frac{n}{i}]\\
&=\sum_{i | n} m^i \varphi(\frac{n}{i}) \sum_{j | \gcd(m,\frac{n}{i})}\varphi(j)\\
&=\sum_{i | n} m^i \varphi(\frac{n}{i}) \gcd(m,\frac{n}{i})
\end{aligned}
\]
这东西就好做了,直接一个调和级数\(O(n\log n)\)带走
点我看代码o( ̄▽ ̄)d
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const LL P = 998244353;
const int U = 1e6;
int T;
const int N = 1e6 + 10;
LL ans, n, m, f[N];
LL p[N], vis[N], tot, phi[N], inv[N];
LL invn, g[N], pw[N];
void Sieve() {
phi[1] = 1;
for(int i = 2; i <= U; ++i) {
if(!vis[i]) p[++tot] = i, phi[i] = i - 1;
for(int j = 1; j <= tot; ++j) {
int v = p[j] * i;
if(v > U) break;
vis[v] = 1;
if(i % p[j] == 0) {
phi[v] = phi[i] * p[j];
break;
}
phi[v] = phi[i] * phi[p[j]];
}
}
}
LL gcd(LL x, LL y) {return y == 0 ? x : gcd(y, x % y);}
LL fpow(LL x, LL pnt = P - 2) {
LL res = 1;
for(; pnt; pnt >>= 1, x = x * x % P) if(pnt & 1) res = res * x % P;
return res;
}
int main() {
read(T);
Sieve();
while(T--) {
ans = 0;
read(n), read(m);
for(int i = 1; i <= n; ++i) inv[i] = fpow(i);
for(int i = 1; i <= n; ++i) f[i] = 0;
pw[0] = 1; for(int i = 1; i <= n; ++i) g[i] = gcd(m, i), pw[i] = pw[i - 1] * m % P;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j * i <= n; ++j) {
f[i * j] = (f[i * j] + phi[j] * pw[i - 1] % P * g[j] % P * inv[i * j] % P) % P;
}
}
for(int i = 1; i < n; ++i) printf("%lld ",f[i]);
printf("%lld\n",f[n]);
}
}
最新文章
- 将css和js缓存到localStorage缓存,提高网页响应速度
- 计算机网络学习笔记--网络层之IP地址与子网
- Webwork 学习之路【08】结合实战简析Controller 配置
- tk画图
- hdu 3622 Bomb Game(二分+2-SAT)
- ES6,ES2105核心功能一览,js新特性详解
- linux 免交互状态下修改用户密码
- ffmpeg内置aac编码器正式发布
- android studio 安装总结
- 简单三步为Azure安装 Visual Studio
- ACM——A + B Problem (4)
- Activity与Service之间交互并播放歌曲的实现代码
- C#弹出对话框
- Shell Script - 追踪与debug
- Django 提交 form 表单(使用sqlite3保存数据)
- # xrdp 在linux deploy 折腾记录
- oracle:TNS:监听程序无法分发客户机连接
- java-使用icepdf实现pdf转换成png
- 关于Image创建的内存管理
- 时间格式—My97DatePicker控件使用