自动搬运

查看原文

来自洛谷，原作者为

	do_while_true 水

搬运于2025-08-24 22:28:19，当前版本为作者最后更新于2023-05-22 23:49:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

快进完生成函数，现在我们知道如果令一个长度为 $i$ 的连续段权值为 $in[z^i]\frac{z^2}{1-z+z^2}$，一个连续段权值的 ogf 是 $F$，那么答案的 ogf 就是 $\frac{1}{1-F}$．

先看看 $\frac{z^2}{1-z+z^2}$ 展开，发现形式很好看，就是 $\{0,0,1,1,0,-1,-1,0,1,1,0,-1,-1,\cdots\}$，后面就是 $\{0,1,1,0,-1,-1\}$ 的循环了。也就是只有 $len\bmod 3=0,2$ 的连续段有权值，并且按照 $\lfloor\frac{len}{3}\rfloor$ 的奇偶性分类。这样我们就能通过记录模 $3$ 为 $0,1,2$ 处的位置的一个前缀和状物（每长度为 $3$ 分组，按照奇偶决定对前缀和贡献为正还是负）就能 $\mathcal{O}(n)$ 递推出来了。

这玩意能矩阵快速幂，但是信息数还是太多了，大概还需要一组一组转移。其实递推 $f_i$ 可以直接考虑 $i$ 所在连续段长度，$\leq 6$ 的直接转，$>6$ 的让它从 $(i-6)$ 那个位置续上。由于权值中需要乘个 $len$，所以续上的时候要多记一个 $g$ 表示只有最后一段没有乘 $len$ 的答案是多少。现在就只需要记 $[i-6,i-1]$ 的所有 $f,g$，信息数是 $12$，先把前 $6$ 个位置递推出来，再矩阵快速幂就 $\mathcal{O}(\log n)$ 复杂度了。

实际上递推式还能更短，跑 BM 对着系数找规律应该能找出来，但我懒了（其实就是不会 BM）。

$\mathcal{O}(n)$：

const int N=100010;
int n;
int f[N];
int s[3],t[3];
signed main(){
	read(n);
	s[0]=f[0]=1;
	for(int i=1;i<=n;i++){
		int o=i%3;
		for(int j=2;j<=3;j++){
			int p=o-j<0?o-j+3:o-j;
			if(((i/3)&1) ^ (o-j<0)){
				cdel(f[i],1ll*n*del(1ll*s[p]*i%mod,t[p])%mod);
			}
			else{
				cadd(f[i],1ll*n*del(1ll*s[p]*i%mod,t[p])%mod);
			}
		}
		if((i/3)&1){
			cdel(s[i%3],f[i]);
			cdel(t[i%3],1ll*f[i]*i%mod);
		}
		else{
			cadd(s[i%3],f[i]);
			cadd(t[i%3],1ll*f[i]*i%mod);
		}
	}
	cout << 1ll*f[n]*qpow(1ll*n*n%mod,mod-2)%mod << '\n';
	return 0;
}

const int N=100020;
int n;
int buff[N],bufg[N];
int *f=buff+10,*g=bufg+10;
signed main(){
	read(n);
	f[0]=g[0]=1;
	for(int i=2;i<=n;i++){
		cadd(f[i],f[i-2]*2ll%mod*n%mod);
		cadd(g[i],1ll*f[i-2]*n%mod);
		cadd(f[i],f[i-3]*3ll%mod*n%mod);
		cadd(g[i],1ll*f[i-3]*n%mod);
		cdel(f[i],f[i-5]*5ll%mod*n%mod);
		cdel(g[i],1ll*f[i-5]*n%mod);
		cdel(f[i],f[i-6]*6ll%mod*n%mod);
		cdel(g[i],1ll*f[i-6]*n%mod);
		if(i!=6){
			cadd(f[i],f[i-6]);
			cadd(f[i],g[i-6]*6ll%mod);
			cadd(g[i],g[i-6]);
		}
	}
	cout << 1ll*f[n]*qpow(1ll*n*n%mod,mod-2)%mod << '\n';
	return 0;
}

$\mathcal{O}(\log n)$：

const int N=100020;
ll n;
int buff[20],bufg[20];
int *f=buff+10,*g=bufg+10;
int a[13][13],b[13][13],c[13][13],ans[13][13];
void mul(int z[13][13],int x[13][13],int y[13][13]){
	memset(c,0,sizeof(c));
	for(int k=1;k<=12;k++)
		for(int j=1;j<=12;j++)
			if(y[k][j]){
				for(int i=1;i<=12;i++)
					if(x[i][k]){
						cadd(c[i][j],1ll*x[i][k]*y[k][j]%mod);
					}
			}
	memcpy(z,c,sizeof(c));
}
signed main(){
	int m=read(n);
	f[0]=g[0]=1;
	for(int i=2;i<=6;i++){
		cadd(f[i],f[i-2]*2ll%mod*n%mod);
		cadd(g[i],1ll*f[i-2]*n%mod);
		cadd(f[i],f[i-3]*3ll%mod*n%mod);
		cadd(g[i],1ll*f[i-3]*n%mod);
		cdel(f[i],f[i-5]*5ll%mod*n%mod);
		cdel(g[i],1ll*f[i-5]*n%mod);
		cdel(f[i],f[i-6]*6ll%mod*n%mod);
		cdel(g[i],1ll*f[i-6]*n%mod);
	}
	if(n<=6){
		cout << 1ll*f[n]*qpow(1ll*n*n%mod,mod-2)%mod << '\n';
		return 0;
	}
	a[2][1]=2ll*n%mod;
	a[2][7]=n%mod;
	a[3][1]=3ll*n%mod;
	a[3][7]=n%mod;
	a[5][1]=del(0,5ll*n%mod);
	a[5][7]=del(0,n%mod);
	a[6][1]=del(1,6ll*n%mod);
	a[6][7]=del(0,n%mod);
	a[12][1]=6;
	a[12][7]=1;
	a[1][2]=1;
	a[2][3]=1;
	a[3][4]=1;
	a[4][5]=1;
	a[5][6]=1;
	a[7][8]=1;
	a[8][9]=1;
	a[9][10]=1;
	a[10][11]=1;
	a[11][12]=1;
	for(int i=1;i<=12;i++)ans[i][i]=1;
	n-=6;
	while(n){
		if(n&1){
			mul(ans,ans,a);
		}
		mul(a,a,a);
		n>>=1;
	}
	int s=0;
	for(int i=1;i<=6;i++)
		cadd(s,1ll*f[7-i]*ans[i][1]%mod);
	for(int i=1;i<=6;i++)
		cadd(s,1ll*g[7-i]*ans[i+6][1]%mod);
	cout << 1ll*s*qpow(1ll*m*m%mod,mod-2)%mod << '\n';
	return 0;
}