題意

對于 \(n\) 個元素的任意排列 \(p\)，給定 \(k\) 和 \(m\)，初始變量 \(x=k\)，定義 \(f(k,m)\) 表示經過 \(m\) 次 \(x \gets p_x\) 變換后 \(x\) 的值，求所有 \(p\) 排列下的 \(x\) 的和對 \(998244353\) 取模后的結果，即求如下式子：

題解

對于任意排列，都可以由若干不相交的環構成，\(x\) 最初也位于一個環上，經過若干次變換后，我們分情況討論，分別是 \(x\) 位于原位置 \(k\) 上，\(x\) 位于環上其他位置

第一種情況

\(x\) 經過若干次變換后仍位于 \(k\) 的位置上，令環長為 \(c\)，顯然 \(c|m\)，對于每一種 \(c\) ，計算他可能出現的排列數量，由于 \(k\) 的值已經確定，我么們需要在剩余 \(n-1\) 個選 \(c-1\) 個元素構成環，有 \(\binom{n-1}{c-1}\) 種方案，由于這 \(c\) 個元素構成了一個環，對這 \(c\) 個元素構造圓排列，注意到任意一個圓排列都對應原來的線排列當中的一種排列情況，不同圓排列對應不同情況且總能合法，所以計算這 \(c\) 個元素的圓排列，為 \(Q_c^c=\left ( c-1 \right ) !\)，表示該環的排列方案數，的接著考慮剩下 \(n-c\) 個元素的排列方案數，顯然為 \(\left ( n-c \right ) !\) 種方案，令這樣的 \(c\) 有 \(d\) 個，即區間 \([1,n]\) 當中 \(m\) 的約數的個數，因為只有當 \(c\) 整除 \(m\) 時，才會時變換后回到原位置，出現第一種，第一種情況的總貢獻是：

第二種情況

\(x\) 經過若干次變換后位于環的其他位置，環長為 \(c\)，顯然 \(c \nmid m\)，這樣的 \(c\) 顯然有 \(n-d\) 個，與第一種情況的分析方法類似，我們先欽定變換后的 \(x\)，則要從剩余 \(n-2\) 個元素里選 \(c-2\) 個元素，有 \(\binom{n-2}{c-2}\) 種方案構成這個環，\(x\) 與 \(k\) 的相對位置不變，因為 \(x\) 相對于 \(k\) 的位置是在環中 \(k\) 往后 \(m \mod c\) 個元素，因此可以把 \(x\) 和 \(k\) 當作一個元素在環中進行圓排列計算，則環的排列有 \(Q_{c-1}^{c-1}=\left ( c-2 \right ) !\) 種方案。剩余 \(n-2\) 個元素有 \(\left ( n-2 \right ) !\) 個排列方案，于是第二種情況的總貢獻是：

總結

將兩種情況算得的答案相加即可，如下：

分析一下時間復雜度，先預處理所有數的階乘，在分解 \(m\) 的因數，時間復雜度為 \(O(n+T\sqrt n)\)。

CODE

#include<cstdio>
using namespace std;

typedef long long ll;
const int P=998244353;
const int N=1e7;
ll Q,n,m,k,fac[N];

void init(){
    fac[0]=1;
    for (int i=1;i<=N;i++) fac[i]=(fac[i-1]*i)%P;
}

int main(){
    init();
    scanf("%lld",&Q);
    while (Q--){
        scanf("%lld%lld%lld",&n,&m,&k);
        ll d=0;
        if (!m) d=n;
        for (int i=1;i*i<=m&&i<=n;i++){
            if (m%i==0){
                if (i*i==m){
                    d++;
                    continue;
                }
                else if (m/i<=n) d+=2;
                else d++;
            }
        }
        ll ans=0;
        ans=(k*fac[n-1]%P*d)%P+((n*(n+1)/2-k)%P*fac[n-2])%P*(n-d)%P;
        ans%=P;
        printf("%lld\n",ans);
    }
    return 0;
}