http://codeforces.com/gym/103102

I. Modulo Permutations

题意：给定 nn，问满足 pi mod pi+1≤2p_i \text{ mod } p_{i+1} \le 2，（pn+1=p1p_{n+1}=p_1），的排列 pp 的个数。

dp

首先 1 和 2 可以放在任意位置。

由于这个题目要的其实是个环，所以可以从 1 的位置切开，变成 1,x,x,x,2,x,x,x,x。1 和 2 把整个排列分成两段。每一段内一定是递减的，因为如果有递增，则 pi mod pi+1=pi>2p_i \text{ mod } p_{i+1}=p_{i}>2。

从小到大遍历，每一轮在上一轮的基础上插入数 ii，考虑把 ii 放在第一段还是第二段。

假设现在枚举到 ii，数组 dp[j]dp[j] 表示与 ii 处于不同段的数中最大的数为 jj 时的方案数。sum[j]sum[j] 表示 jj 的所有因数的 dpdp 值之和，即 ∑d∣jdp[d]\sum\limits_{d|j}dp[d]。

有两种情况：

  1. 把 ii 和 i−1i-1 放在同一段，此时 dp[j],j≠i−1dp[j],j\neq i-1，都不需要更新，因为是否插入了 ii 对方案数没有影响。
  2. ii 和 i−1i-1 不在同一段，此时更新的是 dp[i−1]dp[i-1]。ii 显然在它所在段的第一位，它后面的数 xx 必须要是 i,i−1,i−2i,i-1,i-2 的因数才能满足 i mod x≤2i\text{ mod }x\le 2。因此 dp[i−1]=∑d∣idp[d]+∑d∣i−1dp[d]+∑d∣i−2dp[d]=sum[i]+sum[i−1]+sum[i−2]dp[i-1]=\sum\limits_{d|i}dp[d]+\sum\limits_{d|i-1}dp[d]+\sum\limits_{d|i-2}dp[d]=sum[i]+sum[i-1]+sum[i-2]。

统计答案时遍历 i∈[3,n−1]i\in[3,n-1] 求和。由于一段可能为空，所以还需要 +2。

由于题目需要的是环，所以还要 *n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;

int n;
ll dp[N], sum[N];

int main() {
    scanf("%d", &n);
    if (n == 1) {
        puts("1");
        return 0;
    }
    if (n == 2) {
        puts("2");
        return 0;
    }
    dp[3] = 2;
    for (int i = 1, j; (j = i * 3) <= n; i++) {
        sum[j] = (sum[j] + dp[3]) % mod;
    }
    for (int i = 4; i <= n; i++) {
        dp[i - 1] = (sum[i] + sum[i - 1] + sum[i - 2]) % mod;
        for (int j = 1, k; (k = j * (i - 1)) <= n; j++) {
            sum[k] = (sum[k] + dp[i - 1]) % mod;
        }
    }
    ll ans = 2;
    for (int i = 3; i < n; i++)ans = (ans + dp[i]) % mod;
    printf("%lld\n", ans * n % mod);
    return 0;
}