本文共 9008 字，大约阅读时间需要 30 分钟。
yxy之前有不喜欢打逗号的习惯，giao哪儿养的怪习惯啊233（轻喷
f ( i , j ) f(i,j) f(i,j) 表示有 i i i 行 j j j 列颜色相同 剩下的随便涂 的方案（有重复方案
g ( i , j ) g(i,j) g(i,j) 表示刚好有 i i i 行 j j j 列颜色相同的方案数 （无重复
f ( i , j ) = ∑ x = i n ∑ y = j n ( x i ) ( y j ) g ( x , y ) f(i,j)=\sum_{x=i}^n \sum_{y=j}^n {x\choose i} {y\choose j}g(x,y) f(i,j)=x=i∑ny=j∑n(ix)(jy)g(x,y)
二项式反演
g ( i , j ) = ∑ x = i n ∑ y = j n ( − 1 ) x + y − i − j ( x i ) ( y j ) f ( x , y ) g(i,j)=\sum_{x=i}^n \sum_{y=j}^n {(-1)}^{x+y-i-j}{x\choose i} {y\choose j}f(x,y) g(i,j)=x=i∑ny=j∑n(−1)x+y−i−j(ix)(jy)f(x,y)
那么答案就是
a n s = 3 n 2 − g ( 0 , 0 ) ans=3^{n^2}-g(0,0) ans=3n2−g(0,0)
考虑求 f ( i , j ) f(i,j) f(i,j)
当 i = 0 , j = 0 i=0,j=0 i=0,j=0 时 f ( i , j ) = 3 n 2 f(i,j)=3^{n^2} f(i,j)=3n2
当 i j = 0 ij=0 ij=0 时 f ( i , j ) = ( n i ) ( n j ) 3 n ( n − i − j ) + i + j f(i,j)={n \choose i}{n \choose j}3^{n(n-i-j)+i+j} f(i,j)=(in)(jn)3n(n−i−j)+i+j
当 i j ≠ 0 ij\not=0 ij=0 时 f ( i , j ) = ( n i ) ( n j ) 3 ( n − i ) ( n − j ) + 1 f(i,j)={n \choose i}{n \choose j}3^{(n-i)(n-j)+1} f(i,j)=(in)(jn)3(n−i)(n−j)+1
直接求 g ( 0 , 0 ) g(0,0) g(0,0) 的话会超时 所以推柿子简化一下
g ( 0 , 0 ) = ∑ i = 0 n ∑ j = 0 n ( − 1 ) i + j f ( i , j ) = ∑ i = 1 n ∑ j = 1 n ( − 1 ) i + j f ( i , j ) + 2 × ∑ i = 1 n ( − 1 ) i f ( i , 0 ) + f ( 0 , 0 ) ∑ i = 1 n ∑ j = 1 n ( − 1 ) i + j f ( i , j ) = ∑ i = 1 n ∑ j = 1 n ( − 1 ) i + j ( n i ) ( n j ) 3 ( n − i ) ( n − j ) + 1 = 3 n 2 + 1 ∑ i = 1 n ( − 1 ) i ( n i ) 3 − i n ∑ j = 1 n ( − 1 ) j ( n j ) 3 − j n + i j = 3 n 2 + 1 ∑ i = 1 n ( − 1 ) i ( n i ) 3 − i n ∑ j = 1 n ( n j ) ( − 3 i − n ) j = 3 n 2 + 1 ∑ i = 1 n ( − 1 ) i ( n i ) 3 − i n ( ( 1 − 3 i − n ) n − 1 ) \begin{aligned} g(0,0)&=\sum_{i=0}^n \sum_{j=0}^n {(-1)}^{i+j}f(i,j) \\ &=\sum_{i=1}^n \sum_{j=1}^n {(-1)}^{i+j}f(i,j)+2\times\sum_{i=1}^{n}(-1)^if(i,0)+f(0,0) \\ \sum_{i=1}^n \sum_{j=1}^n{(-1)}^{i+j}f(i,j)&=\sum_{i=1}^n \sum_{j=1}^n{(-1)^{i+j}}{n \choose i}{n\choose j}3^{(n-i)(n-j)+1} \\ &=3^{n^2+1}\sum_{i=1}^n {(-1)^i}{n \choose i}3^{-in} \sum_{j=1}^n{(-1)^{j}}{n\choose j}3^{-jn+ij} \\ &=3^{n^2+1}\sum_{i=1}^n {(-1)^i}{n \choose i}3^{-in} \sum_{j=1}^n{n\choose j}{(-3^{i-n})}^{j} \\ &=3^{n^2+1}\sum_{i=1}^n(-1)^i{n \choose i}3^{-in}({(1-3^{i-n})^n}-1) \end{aligned} g(0,0)i=1∑nj=1∑n(−1)i+jf(i,j)=i=0∑nj=0∑n(−1)i+jf(i,j)=i=1∑nj=1∑n(−1)i+jf(i,j)+2×i=1∑n(−1)if(i,0)+f(0,0)=i=1∑nj=1∑n(−1)i+j(in)(jn)3(n−i)(n−j)+1=3n2+1i=1∑n(−1)i(in)3−inj=1∑n(−1)j(jn)3−jn+ij=3n2+1i=1∑n(−1)i(in)3−inj=1∑n(jn)(−3i−n)j=3n2+1i=1∑n(−1)i(in)3−in((1−3i−n)n−1) 然后就从后往前套娃求解就可了直接求方案数不好求 所以求重复的方案数（方案数指操作序列的方案数
当一个方案存在 k i = j , l j = i − 1 k_i=j,l_j=i-1 ki=j,lj=i−1 就是重复。接下来称这种情况为不合法
按照套路设 f ( i ) f(i) f(i) 为有 i i i 个不合法 剩下的随便取的方案数
设 g ( i ) g(i) g(i) 为刚好有 i i i 个不合法的方案数 则
f ( i ) = ∑ j = i n ( j i ) g ( j ) f(i)=\sum_{j=i}^{n}{j\choose i}g(j) f(i)=j=i∑n(ij)g(j)
二项式反演
g ( i ) = ∑ j = i n ( − 1 ) j − i ( j i ) f ( j ) g(i)=\sum_{j=i}^{n}{(-1)}^{j-i}{j\choose i}f(j) g(i)=j=i∑n(−1)j−i(ij)f(j)
直接按照定义求 f ( i ) f(i) f(i)
f ( i ) = ( n i ) ( m i ) i ! ( n + 1 ) m − i ( m + 1 ) n − i f(i)={n \choose i}{m\choose i}i!(n+1)^{m-i}(m+1)^{n-i} f(i)=(in)(im)i!(n+1)m−i(m+1)n−i
所以答案就是
g ( 0 ) = ∑ i = 0 n ( − 1 ) i ( n i ) ( m i ) i ! ( n + 1 ) m − i ( m + 1 ) n − i g(0)=\sum_{i=0}^{n}{(-1)}^i{n \choose i}{m\choose i}i!(n+1)^{m-i}(m+1)^{n-i} g(0)=i=0∑n(−1)i(in)(im)i!(n+1)m−i(m+1)n−i
（其实容斥好理解些
令 n u m = m i n ( n , m ) num=min(n,m) num=min(n,m)
a n s = ∑ i = 1 n ∑ j = 1 m μ 2 ( g c d ( i , j ) ) = ∑ t = 1 n u m μ 2 ( t ) ∑ i = 1 i t ≤ n ∑ j = 1 i j ≤ m ( g c d ( i , j ) = = 1 ) = ∑ t = 1 n u m μ 2 ( t ) ∑ i = 1 i t ≤ n ∑ j = 1 i j ≤ m ∑ d ∣ i d ∣ j μ ( d ) = ∑ t = 1 n u m μ 2 ( t ) ∑ d = 1 d t ≤ n μ ( d ) ⌊ n d t ⌋ ⌊ m d t ⌋ = ∑ t = 1 n u m ∑ d = 1 d t ≤ n u m μ 2 ( t ) μ ( d ) ⌊ n d t ⌋ ⌊ m d t ⌋ = ∑ d t = 1 d t ≤ n u m ⌊ n d t ⌋ ⌊ m d t ⌋ ∑ t ∣ d t μ 2 ( t ) μ ( d ) \begin{aligned} ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}\mu ^2(gcd(i,j)) \\ &=\sum_{t=1}^{num}\mu ^2(t)\sum_{i=1}^{it\le n}\sum_{j=1}^{ij\le m}(gcd(i,j)==1) \\ &=\sum_{t=1}^{num}\mu ^2(t)\sum_{i=1}^{it\le n}\sum_{j=1}^{ij\le m}\sum_{d|i\ d|j}\mu (d) \\ &=\sum_{t=1}^{num}\mu ^2(t)\sum_{d=1}^{dt\le n}\mu (d){\lfloor\frac{n}{dt}\rfloor}{\lfloor\frac{m}{dt}\rfloor} \\ &=\sum_{t=1}^{num}\sum_{d=1}^{dt\le num}\mu ^2(t)\mu (d){\lfloor\frac{n}{dt}\rfloor}{\lfloor\frac{m}{dt}\rfloor} \\ &=\sum_{dt=1}^{dt\le num}{\lfloor\frac{n}{dt}\rfloor}{\lfloor\frac{m}{dt}\rfloor} \sum_{t|dt}^{}\mu ^2(t)\mu (d) \end{aligned} ans=i=1∑nj=1∑mμ2(gcd(i,j))=t=1∑numμ2(t)i=1∑it≤nj=1∑ij≤m(gcd(i,j)==1)=t=1∑numμ2(t)i=1∑it≤nj=1∑ij≤md∣i d∣j∑μ(d)=t=1∑numμ2(t)d=1∑dt≤nμ(d)⌊dtn⌋⌊dtm⌋=t=1∑numd=1∑dt≤numμ2(t)μ(d)⌊dtn⌋⌊dtm⌋=dt=1∑dt≤num⌊dtn⌋⌊dtm⌋t∣dt∑μ2(t)μ(d) 观察到 ∑ t ∣ d t u 2 ( t ) u ( d ) \sum_{t|dt}^{}u^2(t)u(d) ∑t∣dtu2(t)u(d) 是两个积性函数卷起来的形式 所以接下来考虑质数次方处的值 我们发现只要在 p 2 p^2 p2 处有值 且值为 μ ( p ) \mu(p) μ(p)所以 ∑ t ∣ d t u 2 ( t ) u ( d ) = ( d t = = x ) μ x \sum_{t|dt}^{}u^2(t)u(d)=(\sqrt {dt}==x)\mu_x ∑t∣dtu2(t)u(d)=(dt==x)μx 预处理根号部分的就麻油啦
设 f ( i ) f(i) f(i) 为有 i i i 个空选对 剩下的随便选的方案数， g ( i ) g(i) g(i) 为刚好有 i i i 个空选对的方案数 那么
f ( i ) = ( k i ) ( n − i k − i ) ( k − i ) ! = ∑ j = i k ( j i ) g ( i ) 二 项 式 反 演 一 下 g ( i ) = ∑ j = 1 k ( − 1 ) j − i ( j i ) f ( j ) = ∑ j = 1 k ( − 1 ) j − i ( j i ) ( k j ) ( n − j k − j ) ( k − j ) ! \begin{aligned} f(i)&={k\choose i}{n-i\choose k-i}(k-i)! \\ &=\sum_{j=i}^{k}{j\choose i}g(i) \\ 二项式反演一下 \\ g(i)&=\sum_{j=1}^k{(-1)}^{j-i}{j\choose i}f(j) \\ &=\sum_{j=1}^k{(-1)}^{j-i}{j\choose i}{k\choose j}{n-j\choose k-j}(k-j)! \end{aligned} f(i)二项式反演一下g(i)=(ik)(k−in−i)(k−i)!=j=i∑k(ij)g(i)=j=1∑k(−1)j−i(ij)f(j)=j=1∑k(−1)j−i(ij)(jk)(k−jn−j)(k−j)! 答案就是 g ( x ) g(x) g(x)设 f ( i ) f(i) f(i) 为强制 i i i 条边不被染色 剩下的点在联通块内随便配对的方案数。
那么
f ( i ) = ∑ j = i n ( j i ) g ( j ) f(i)=\sum_{j=i}^n{j\choose i}g(j) f(i)=j=i∑n(ij)g(j)
所以
g ( i ) = ∑ j = i n ( − 1 ) j − i ( j i ) f ( j ) g(i)=\sum_{j=i}^n{(-1)}^{j-i}{j\choose i}f(j) g(i)=j=i∑n(−1)j−i(ij)f(j)
g ( 0 ) = ∑ i = 0 n ( − 1 ) i f ( i ) g(0)=\sum_{i=0}^n{(-1)}^if(i) g(0)=i=0∑n(−1)if(i)
设 d p ( x , y ) dp(x,y) dp(x,y) 表示在 x x x 子树内， x x x 所在的联通块大小是 y y y 的所有方案的容斥系数和（不算 x x x 所在块的贡献）
那么就有转移。
d p ( x , y + z ) ← d p ( x , y ) × d p ( s o n , z ) dp(x,y+z)\ \ \leftarrow\ \ dp(x,y)\times dp(son,z) dp(x,y+z) ← dp(x,y)×dp(son,z)
d p ( x , y ) ← − ( z − 1 ) ！ ！ d p ( x , y ) × d p ( s o n , z ) dp(x,y)\ \ \leftarrow\ \ -(z-1)！！dp(x,y)\times dp(son,z) dp(x,y) ← −(z−1)！！dp(x,y)×dp(son,z)
枚举 y y y 和 z z z 即可，因为每对点只会在他们的 l c a lca lca 处算一次 所以最后时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
每个权值的贡献的系数是一样的 所以我们就把题目转化为求这个系数 则
a n s s u m = ∑ i = 1 n i ( n − 1 i − 1 ) S ( n − i , k − 1 ) = ∑ i = 1 n i ( n − 1 i − 1 ) ∑ j = 0 k − 1 ( − 1 ) k − 1 − j ( k − 1 − j ) ! j n − i j ! = ∑ j = 0 k − 1 ∑ i = 1 n ( n − 1 i − 1 ) i ( − 1 ) k − 1 − j ( k − 1 − j ) ! j n − i j ! = ∑ j = 0 k − 1 ( − 1 ) k − 1 − j ( k − 1 − j ) ! j ! ∑ i = 1 n i ( n − 1 i − 1 ) j n − i ∑ i = 1 n i ( n − 1 i − 1 ) j n − i = ∑ i = 1 n ( n − 1 i − 1 ) j n − i + ∑ i = 1 n ( i − 1 ) ( n − 1 i − 1 ) j n − i = ( j + 1 ) n − 1 + ( n − 1 ) ∑ i = 1 n ( n − 2 i − 2 ) j n − i = ( j + 1 ) n − 1 + ( n − 1 ) ( j + 1 ) n − 2 = ( n + j ) ( j + 1 ) n − 2 a n s = s u m ∑ j = 0 k − 1 ( − 1 ) k − 1 − j ( k − 1 − j ) ! j ! ( n + j ) ( j + 1 ) n − 2 \begin{aligned} \frac{ans}{sum}&=\sum_{i=1}^{n}i{n-1\choose i-1}S(n-i,k-1) \\ &=\sum_{i=1}^{n}i{n-1\choose i-1} \sum_{j=0}^{k-1}\frac{ {(-1)}^{k-1-j}}{(k-1-j)!} \frac{j^{n-i}}{j!} \\ &=\sum_{j=0}^{k-1}\sum_{i=1}^{n} {n-1\choose i-1} i\frac{ {(-1)}^{k-1-j}}{(k-1-j)!} \frac{j^{n-i}}{j!} \\ &=\sum_{j=0}^{k-1} \frac{ {(-1)}^{k-1-j}}{(k-1-j)!j!} \sum_{i=1}^{n} i{n-1\choose i-1}{j}^{n-i} \\ \\ \sum_{i=1}^{n} i{n-1\choose i-1}{j}^{n-i}&= \sum_{i=1}^{n}{n-1\choose i-1}{j}^{n-i}+\sum_{i=1}^{n}(i-1){n-1\choose i-1} {j}^{n-i} \\ &={(j+1)}^{n-1}+(n-1)\sum_{i=1}^{n}{n-2\choose i-2}{j}^{n-i} \\ &={(j+1)}^{n-1}+(n-1){(j+1)}^{n-2} \\ &=(n+j){(j+1)}^{n-2} \\ \\ ans&=sum\sum_{j=0}^{k-1} \frac{ {(-1)}^{k-1-j}}{(k-1-j)!j!}(n+j){(j+1)}^{n-2} \end{aligned} sumansi=1∑ni(i−1n−1)jn−ians=i=1∑ni(i−1n−1)S(n−i,k−1)=i=1∑ni(i−1n−1)j=0∑k−1(k−1−j)!(−1)k−1−jj!jn−i=j=0∑k−1i=1∑n(i−1n−1)i(k−1−j)!(−1)k−1−jj!jn−i=j=0∑k−1(k−1−j)!j!(−1)k−1−ji=1∑ni(i−1n−1)jn−i=i=1∑n(i−1n−1)jn−i+i=1∑n(i−1)(i−1n−1)jn−i=(j+1)n−1+(n−1)i=1∑n(i−2n−2)jn−i=(j+1)n−1+(n−1)(j+1)n−2=(n+j)(j+1)n−2=sumj=0∑k−1(k−1−j)!j!(−1)k−1−j(n+j)(j+1)n−2f ( n ) f(n) f(n) 在质数处为 − 1 -1 −1 ，有平方因子时为 0 0 0 ，其余为 1 1 1 。
考虑算出无平方因子的个数，再减去质数的个数。
算质数的个数就是 M i n 25 Min25 Min25 筛计算。时间 O ( n 0.75 log n ) O(\frac{n^{0.75}}{\log n}) O(lognn0.75) 。
无平方因子的个数也就是算 ∑ μ 2 \sum \mu^2 ∑μ2 ，记 p ( x ) = max d 2 ∣ x { d } p(x)=\max_{d^2|x}\{d\} p(x)=maxd2∣x{ d}
∑ i = 1 n μ 2 ( i ) = ∑ i = 1 n [ p ( i ) = 1 ] = ∑ d = 1 n μ ( d ) ⌊ n / d 2 ⌋ P S : H x 表示 p 是 x 的倍数的数的个数， h x 表示 p 是 x 的数的个数，莫比乌斯反演一下即可 \begin{aligned} &\sum_{i=1}^n \mu^2(i) \\ =&\sum_{i=1}^{n}[p(i)=1] \\ =&\sum_{d=1}^{n}\mu(d)\lfloor n/d^2\rfloor\\ & PS: H_x\text{ 表示 }p \text{ 是 }x\text{ 的倍数的数的个数， }\\ &h_x \text{ 表示 }p \text{ 是 }x\text{ 的数的个数，莫比乌斯反演一下即可 } \end{aligned} ==i=1∑nμ2(i)i=1∑n[p(i)=1]d=1∑nμ(d)⌊n/d2⌋PS:Hx 表示 p 是 x 的倍数的数的个数， hx 表示 p 是 x 的数的个数，莫比乌斯反演一下即可 第一步到第二步就是莫比乌斯反演一下就可以了。已经时个整除分块的形式了， O ( n ) O(\sqrt n) O(n) 计算答案。发表评论
最新留言
关于作者
