「题解」P7275 计树
do_while_true
·
·
题解
快进完生成函数，现在我们知道如果令一个长度为 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）。
```cpp
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;
}
```
```cpp
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)$：
```cpp
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;
}
```