本文共 3693 字，大约阅读时间需要 12 分钟。

题目

题目背景

——然后他就投胎当了猪。

题目描述

为了产生交错的美感，要求金色的连续段长度不超过 $k$ 。即，任意 $k+1$ 个连续的珠子，都不全是金色。

现在请问，不同的手环有多少种？补充一句，手环是可以旋转的，但是不可以翻转；珠子只有颜色的区别。形式化地说，记金色为 $1$，白色为 $0$，两个手环形成的颜色序列（从任意一个珠子开始，顺时针写下每个珠子的颜色）分别是 $⟨a_0,a_1,\dots ,a_{n-1}⟩,⟨b_0,b_1,\dots ,b_{n-1}⟩$，如果存在一个正整数 $t$ 使得 $a_{(i+t)\mathrm{m}\mathrm{o}\mathrm{d}n}=b_i$，那么这两个手环是相同的。

输出方案数对 $998244353$ 取模的结构。

数据范围与提示

思路

显然是 $\mathtt{b}\mathtt{u}\mathtt{r}\mathtt{n}\mathtt{s}\mathtt{i}\mathtt{d}\mathtt{e}$ 嘛。我其实也忘了许多，但是记得证明的思路，现场重推了一下。

顺时针旋转 $x$ 的操作下，不动点是 $a_{(i+x)\mathrm{m}\mathrm{o}\mathrm{d}n}=a_i$，显然就是周期 $T=\gcd (x,n)$ 嘛。只需要确定前 $T$ 个珠子的颜色，剩下的就都确定了。

不妨设 $m<n$，那么至少有一个白色珠子，所以 $T$ 中也含有一个白色珠子。真正的手环是 $T$ 复制若干次得到的，不难发现，其金色连续段要么完全在 $T$ 中，要么是 $T$ 首尾相接。

问题转化为，对于一个 $T$ 个点的环，求金色连续段长度不超过 $k$ 的方案数。不过这个环是不能旋转的（即，旋转相同视为不同方案）。

如果用 $\mathtt{d}\mathtt{p}$ 来做，大概就是 $f(i,j)={\sum }_{t=0}^{k}f(i-1,j-t-1)$ 的样子。然后你发现它很像母函数。事实上的确如此——将一个金色连续段与它右边的一个白色珠子看成一个物品，每个物品的选择数量不同，则方案不同。用 $x$ 的指数代表 金色珠子的数量，则

为什么是 $n-m-1$ 次方？因为一共有 $n-m$ 个白色珠子，而最后一个是首尾相接，特殊处理，所以剩下的是 $n-m-1$ 次方。（毕竟每个物品恰好提供一个白色珠子。）

首尾相接其实很好处理。对于长度为 $i+1$（即，有 $i$ 的情况，可以在末尾出现 $[1,i+1]$ 个珠子（剩下的就放在开头），所以方案数就是 $i+1$ 了。即

二者乘起来的第 $m$ 项系数就是答案。

那么这里有一个推式子的做法，把 $G(x)$ 解出来，然后 ${\sum }_{i=0}^k{x}^i=\frac{1-x^{k+1}}{1-x}$ 的 $n-m-1$ 次幂就分别计算分子分母。化简式子之后，大概是 $($ 三项的多项式 $)$ $\times$ $($ 二项式展开式 $)$ $\times$ $($ 二项式展开式 $)$ 。枚举三项多项式中的一项，再 $m_k=\lfloor \frac{m}{k}\rfloor$ 枚举 $1-x^{k+1}$ 的二项式展开式中的一项，直接就找到了 $1-x$ 的二项式展开式中的一项。

最神奇的是，暴力计算非常快。因为每一项要么取 $\frac{1}{1-x}$，要么取 $\frac{-x^{k+1}}{1-x}$，直接枚举第二类的数量（其不超过 $m_k$ 个），除以了 $x^{k+1}$ 后全部变为 $\frac{1}{1-x}$，可以组合数直接计算。——从现实意义来看，就是 容斥原理 计算不超过 $k$ 个的方案数。由于 $G(x)$ 只有 $k$ 次，我们只需要求出 $(m-k)$ 次到 $m$ 次项，这是 $\mathcal{O}(k\cdot m_k)=\mathcal{O}(m)$ 的。

然后枚举 $G(x)$ 中的一项，乘上上面算出的一项。我们就已经得到了答案。

但是为何我不敢这么打？因为我不会算复杂度。每次计算是 $\mathcal{O}(m)$ 的，但是这里的 $m$ 不是题目中直接输入的 $m$，而是 $T$ 里面有多少个金色的珠子。如果枚举一个 $d=n/T$（即周期的个数），可知复杂度为

糟糕透顶的情况是 $m\mid n$，此时复杂度是 $m$ 的因数和 ${\sigma }_1(m)=\prod \frac{p_i^{t_i+1}-1}{p_i-1}$，其中 $m=\prod p_i^{t_i}$ 表示质因数分解。这东西是近乎线性的（打表证明）。

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long int_;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}const int Mod = 998244353;inline int qkpow(int_ b,int_ q){   	int_ a = 1;	for(; q; q>>=1,b=b*b%Mod)		if(q&1) a = a*b%Mod;	return a;}int n, m, k;namespace MyMath{   	const int MaxN = 3000005;	int jc[MaxN], inv[MaxN];	void importC(){   		jc[1] = inv[1] = 1;		for(int i=2; i
       
         primes;	void importPhi(){   		phi[1] = 1; // important		for(int i=2; i