题解：P10744 [SEERC2020] Modulo Permutations

OtterZ · 2024-11-21 14:04:02 · 题解

题目

求有多少个全排列，使 p_i\bmod p_{i \bmod n + 1} \le 2。

要求长度为 n(1 \le n \le 10 ^ 6)。

引理

引理：每一个排列从一个位置开始环形遍历，可得到结尾分别为 1,2 的单调下降序列拼合得到的全排列。

证：对于 p_i < p_{i \bmod n + 1},p_i > 2，有 p_i \mod p_{i \bmod n + 1} = p_i > 2，故而 p_i > 2 时总有 p_i > p_{i \bmod n + 1}，而 p_i < p_{i \bmod n + 1},p_i \le 2，有 p_i \bmod p_{i \bmod n + 1} = p_i \le 2，由此可得，每一个排列从一个位置开始环形遍历，可得到结尾分别为 1,2 的单调下降序列拼合得到的全排列，证毕。

动规

对于其中一个下降子序列，每个数前可接：

我们设 dp_{i,j} 为两序列结尾较小值为 i，较大值为 j 的对应排列数，根据 \max\{i,j\} + 1 的插入情况可得到转移方程。

优化

再来一个引理

引理：设 s_i = \{x|j \in N^+,x \bmod i \le 2 \text{且} x > i + 1\}，有 dp_{i,i + 1} = 1 + \sum_{k \in s_i}dp_{k - 1,k}。

证：对于一个序列结尾为 i，另一个序列结尾为 i + 1,i 前为 k 时，i + 2,i + 3,...,k - 1 此时在另一个序列上，即 i + 1 前，此时得到一个合法结果，还有一个情况，即将所有 x > i 放在另一个序列中也会得到一个合法解。

证毕。

基于引理的快速动规

我们要的答案为 dp_{1,2} \times n，根据引理得到的公式可 \operatorname{O}(n\ln n) 得出，这样就解决了问题。

注意 n = 1 的特殊情况和转移方程的范围判断与去重。

代码

#include<cstdio>
using namespace std;
int n,m,dp[1000009];
int ans;
#define mod 1000000007
int main(){
    scanf("%d",&n);
    if(n == 1){
        puts("1");
        return 0;
    }
    dp[n - 1] = 1;
    ans = 1;
    for(int i = n - 2; i > 0; i --){
        dp[i] = 1;
        for(int j = 1; j * i <= n; j ++){
            if(j * i > i + 1){ //(i,i + 1) -> (j * i - 1,j * i) 
                dp[i] = (dp[i] + dp[i * j - 1]) % mod;
            }
            if(j * i > i && j * i + 1 <= n && i > 1){//(i,i + 1) -> (j * i,j * i + 1)
                dp[i] = (dp[i] + dp[i * j]) % mod;
            }
            if(j * i + 1 > i && j * i + 2 <= n && i > 2){//(i,i + 1) -> (j * i + 1,j * i + 2)
                dp[i] = (dp[i] + dp[i * j + 1]) % mod;
            }
        }
    //  printf("%d\n",dp[i]);
    }
    printf("%d\n",1ll * dp[1] * n % mod);
}