忒魔幻叻，，，

比赛过程

开幕还是巨大多读题，从后往前读了好几题。冯佬发现 M 有人过，仔细一看就是个憨批题……然后很快就 A 了。

冯佬随后给我扔了 G，我想了一下，不同质数的游戏是独立的，然后不同连续段的游戏也是独立的。打了一下连续段的 SG 函数的表，发现就是 Nim 游戏罢了。不过这个题\(a_i\)巨大，所以拿了冯佬上场 cf 的 Pollard’s rho 板子，然后交上去就 T 了……

接下来我打印了一下代码，开始研究怎么优化质因数分解以外的部分，极致优化后还是 T……没办法了，先放一边，这期间 bzy 过了 J。然后我去看 E，感觉这就是个我非常熟悉的题目，几乎见过连名字都一样的题……不过就是缺个带花树板子，抄了一下冯佬带的 Claris 板子交上去第一个点就 T 了，百思不得其解……换了个板子又开始在 WA 和 RE 间横跳，但本地各种或特殊或普通的数据都调不出毛病。

冯佬过了 A 之后开始看 G 代码里质因数分解部份的问题，发现 T 的原因是没法高效的处理两个接近\(10^9\)的大质数乘积的分解（冯佬：「md 上场 cf 怎么没卡我……」）。找了一个神仙板子，然后过了。

最最最牛批的事，赛后我们都发现见到了一些非常非常熟悉的题，最后得出结论：这场 OpenCup 事我们带一寒假打的一场 PTZ Camp。那个时候过了两题自闭了（很乐的事是我记得当时我也是抄板子但过了 E），补题工作也没好好做，然后就成这样子了……

补题：C

题意

给定整数\(n\)，我们称一个序列是好的当且仅当其中元素都是\([1,n]\)中整数且其任意非空子序列的和都不是\(n\)的倍数。

再给定\(k\)，求出长度为\(n-k\)的好序列有多少种。答案对\(p=998244353\)取模。

\(1\le k\le\frac n 4<n<p\)。

解析

首先\(n\)是一定不能选的，下面都在不选\(n\)的基础上考虑。

对于任一好序列，我们假设其众数为\(x\)，而不是\(x\)的数的出现次数为\(t\)。那么，考虑将序列中一部分数配对使得每个对内两数不同，这种对最多能造出\(\min(t,\lfloor\frac{n-k}{2}\rfloor)\)种。然后，我们重新排一下序列，使得每个对中的两个数是相邻的，这个序列的前缀和（算上\(0\)）显然有\(n-k+1\)种。对于任意一对，若我们将这对在新序列中颠倒，那么有且仅有一个前缀和会变化。算上这类新前缀和，可能的前缀和有\(n-k+1+\min(t,\lfloor\frac{n-k}{2}\rfloor)\)种。注意，这些前缀和必须（在模\(n\)意义下）两两不同。这要求至少有\(n-k+1+\min(t,\lfloor\frac{n-k}{2}\rfloor)\le n\)，此中若将取最小的式子代以\(\lfloor\frac{n-k}{2}\rfloor\)则不等式不能成立，因此必须代\(t\)。再做化简得到\(t\le k-1\)，这样\(x\)的出现次数为\(n-k-t\ge n-2k+1\ge n-\frac n 2 + 1> \frac n 2\)。注意到，任意\(n\)的非平凡因子都不超过\(\frac n 2\)，这就要求了\(x\)必须得和\(n\)互质，这样\(x\)的取法有\(\varphi(n)\)种。

下面我们为了讨论方便，做一个变换：将序列中所有元素都在模\(n\)意义下除\(x\)。这个变换是双射所以问题还是一样的，而且此时的\(x\)都变成了\(1\)。首先这个序列中的元素都要小于\(\frac n 2\)，不然可以和一些\(1\)拼成\(n\)。我们将现在不是\(1\)的元素挑出来从小到大排序，若这些元素的和\(s_2\)不小于\(\frac n 2\)，那么其前缀和里总有一个值在\([\frac n 2, n]\)中的，这样还是能和若干\(1\)拼成\(n\)，所以这些元素的和必须要小于\(\frac n 2\)。最后，我们来说明所有元素的和小于\(n\)：若这和\(s\)大于等于\(n\)，那么我们在其中删去若干\(1\)能得到从\(s_2\)到\(s\)的每一个值，这样能构造出和为\(n\)的子序列了，矛盾。但是，显然的，若所有元素和小于\(n\)，那么必然会是好的序列，说明这条件是好序列的充要条件。而且，对于任意和小于\(n\)的序列，其中\(1\)的出现次数必然至少要为\(\frac n 2\)次，不然的话序列总长度不小于\(\frac 3 4 n\)，这样和会大于\(n\)，矛盾。然后下面的问题就是且仅是讨论和小于\(n\)的序列的方案数怎么求了，用隔板法可以知道方案数为\(\binom{n-1}{n-k}\)。

综上，总方案数为\(\binom{n-1}{n-k}\cdot\varphi(n)\)。这里\(n,k\)范围都较大，故组合数可以用分块打表预处理阶乘的方式来做。

代码

#include <bits/stdc++.h>

using ll = long long;
const ll ha = 998244353;
ll V[4992] = {...}; // 打表部分，此处略去

ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(b & 1) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2);
}
ll calc_fac(ll n) {
  ll blk = n / 200000;
  ll res = V[blk];
  for(ll i = blk * 200000 + 1; i <= n; i ++) {
    res = res * i % ha;
  }
  return res;
}
ll calc_C(ll n, ll m) {
  ll ret = calc_fac(n);
  ret = ret * inv(calc_fac(m)) % ha;
  ret = ret * inv(calc_fac(n - m)) % ha;
  return ret;
}

ll phi(ll n) {
  ll ret = n;
  for(ll i = 2; i * i <= n; i ++) {
    if(n % i == 0) {
      ret /= i; ret *= i - 1;
      while(!(n % i)) n /= i;
    }
  }
  if(n > 1) {
    ret /= n; ret *= n - 1;
  }
  return ret;
}

int main() {
  ll n, k; std::cin >> n >> k;
  ll ans = calc_C(n - 1, n - k) * phi(n) % ha;
  std::cout << ans << '\n';
  return 0;
}