题解：P13902 「KFCOI Round

题意

给定一个整数，有一个的排列，下标从开始。最初。

现在需要对数列进行操作。具体地，移动由另一个的排列决定：

在每一步中，。

每一步有两种分类方式：

若数对满足：且，则在同一组中。
若数对满足：且，则在同一组中。

对于每个步骤，可以任意选择分类方式。要求对于两个不同的步骤，满足如果分类方式相同，那么对于每个都满足其所属的组的大小相同。求满足条件的排列的数量。

思路

首先，一定是一个满足条件的排列。其次，如果第步和第步满足要求，那么后续的步骤一定也满足要求，至于为什么，请读者感性理解：第一步已经满足要求，那么第步和第步满足条件，就等价于第步和第步满足条件。所以，我们考虑由这个排列进行变换得到其他的答案。

首先，如果，那么随便一个的排列都可以作为答案，输出。

接下来，讨论一般情况。应该先固定之间的关系，再去处理之间的关系。

考虑这种情况：

如果将相同颜色的格子视为整体，交换顺序，那么显然答案将会符合条件：两种分类方式的大小均未改变。语言有些抽象，请看代码理解。

接下来考虑另一种：

如果将相同颜色的格子视为整体，交换顺序，那么同样答案将会符合条件。

所以，答案为？NO，显然不是。如果怎么办呢？下面讨论这种情况。

考虑第一种：如果此时仍然按照上述方式交换全部，那么不能保证间的关系。

考虑第二种：同样，交换全部关系不满足。

我们得想一种新的方法。对于第一种情况，如果我们交换完整的颜色部分，那么答案是满足条件的。如果我们单独交换不完整的颜色部分，那么答案同样满足条件。

然后，对于第二种情况，如果我们交换完整的颜色部分，那么答案也是满足条件的。

所以，在的情况下，答案为。

代码

lines

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 5e5 + 10, MOD = 1e9 + 7;

int n, m;
ll fac[MAXN];

void Solve() {
  cin >> n >> m;
  if (n < m) {
    cout << fac[n] << '\n';
    return;
  }
  cout << (n % m ? fac[n % m] * fac[m - n % m] % MOD * fac[n / m] % MOD: fac[n / m] * fac[m] % MOD) << '\n';
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
  int T;
  for (cin >> T; T--; Solve());
  return 0;
}