题目内容

曾经有一个叫做塔子哥的数学家，他对数学有着极大的热情和天赋。有一天，他提出了一个非常有趣的问题，他想要计算一个长度为 $n$ 的数组的所有排列中，相邻两数乘积为奇数的对数之和。他将这个值定义为这个数组的权值，用符号 $w(a_1,a_2,\cdots,a_n)$ 表示。比如说，对于数组 $[4,3,1,5,2]$ 来说，它的权值就是 $w(4,3,1,5,2)=2$，因为有两对相邻的元素乘积为奇数：$3*1=3$，$1*5=5$。

思路:贡献计数

其实直觉想想就能做了。但是我这里提供一个稍微严格一点的推导,供大家学习，对之后分析更复杂的情况，学习莫比乌斯反演，Min_25筛等恶心的推式子的东西或许有些用。过程并不简洁，只是力求每一步都清晰，都能满足《Concrete Mathematics: A Foundation for Computer Science》 第二章给出的原则。大佬轻喷

按题目的定义，可以发现是求解

$$\Large \sum_{p \in P_n} \sum_{i=1}^{n-1}\ [p_i是奇数且p_{i+1}是奇数] $$

为了我们后续更好的处理，将 逻辑与 化简成乘法：

$$\Large \sum_{p \in P_n} \sum_{i=1}^{n-1}\ [p_i是奇数]*[p_{i+1}是奇数] $$

不难发现,两个求和符号之间是独立的.可以交换两个求和符号的次序。

可以理解为，从 先考虑排列再考虑位置 到 先考虑位置再考虑排列.

$$=\Large \sum_{i=1}^{n-1} \sum_{p \in P_n} \ [p_i是奇数]*[p_{i+1}是奇数] $$

进一步的，枚举这两个相邻的数$p_i,p_{i+1}$**具体是什么 **

$$=\Large \sum_{i=1}^{n-1} \sum_{p_i\in [1,n]}^{}\ \sum_{p_{i+1}\in[1,n] \wedge p_i \neq p_{i+1}}^{} (\sum_{p \in P_n/\{p_i,p_{i+1}\}}^{} \ [p_i是奇数]*[p_{i+1}是奇数]) $$

不难发现，后面那两个艾弗森符号与第四个求和符号独立，提出来。放到对应的求和符号处

$$=\Large \sum_{i=1}^{n-1} \sum_{p_i\in [1,n] }^{}\ [p_i是奇数]*\sum_{p_{i+1}\in[1,n] \and p_i \neq p_{i+1}}^{} [p_{i+1}是奇数]*(\sum_{p \in P_n/\{p_i,p_{i+1}\}}^{} \ 1) $$

令$odd = \{2k+1|k \geq 0 \wedge 2k+1 \leq n\}$ , 将艾弗森符号放入求和符号的限制条件中，上式等价于

$$=\Large \sum_{i=1}^{n-1} \sum_{p_i\in odd}^{n}\ \sum_{p_{i+1}\in odd \and p_i \neq p_{i+1}}^{n} (n-2)! $$

$(n-2)!$ 与外层三个求和符号无关，提出来

$$=\Large (n-2)! \sum_{i=1}^{n-1} \sum_{p_i\in odd}^{n}\ \sum_{p_{i+1}\in odd \and p_i \neq p_{i+1}}^{n} 1 $$

观察到第2，3个求和符号等价于从$odd$中取两个元素。所以

$$=\Large (n-2)! \sum_{i=1}^{n-1}\binom{|odd|}{2}$$ $$=\Large \binom{\lceil \frac{n}{2} \rceil}{2} (n-2)! \sum_{i=1}^{n-1}1 $$$$=\Large \binom{\lceil \frac{n}{2} \rceil}{2} (n-1)! $$

代码

Java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = (int)(1e9 + 7);
        long f = 1;
        for (int i = 1 ; i <= n - 2 ; i++) f=f*i% mod;
        long odd = (n + 1) / 2;
        long c = (odd - 1) * odd / 2;
        long ans = c * 2 % mod;
        ans = ans * (n - 1) % mod;
        ans = ans * f % mod;
        System.out.println(ans);
    }
}