多校A层冲刺NOIP2024模拟赛08 排列

一种连续段 dp 的解法。

题面

小 Y 最近在研究组合数学，他学会了如何枚举排列。

小 Z 最近在研究数论，他学会了求最大公约数。

于是小 Y 和小 Z 联手出了一个有趣的题目：

有多少个长度为 \(n\) 且任意相邻两个数的最大公约数都不为 \(k\) 的排列？

然而他们并不会做这个题，所以请你来帮帮他们吧！

思路

设 \(dp[i][j]\) 为插入了 \(1\sim i\)，形成了 \(j\) 个连续段，且合法的情况。

强制让两两间 \(gcd\) 为 \(k\) 的数划分到不同的段，这样在最终的排列中 \(gcd\) 为 \(k\) 的数一定不会相邻。

接着发现只有 \(k\) 的倍数的 \(gcd\) 有可能为 \(k\)。

故把 \(k\) 的倍数进行全排列，在排列的基础上划分段，若在排列中两两间的 \(gcd\) 为 \(k\) 则强制划分为两段，否则可划分可不划分，并将划分成 \(j\) 段的方案数加至 \(dp[0][j]\) 中。

然后之间进行朴素的连续段 dp 即可。

CODE

// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 998244353

const int maxn=3005;

int n,k,m;
int p[15],gcd[15][15];

ll dp[maxn][maxn],fac[20],inv[20];

bool vis[15];

inline ll ksm(ll x,ll y)
{
    ll sum=1;
    for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;
    return sum;
}
inline void init()
{
    fac[0]=1;
    for(int i=1;i<=15;i++) fac[i]=fac[i-1]*i%mod;
    inv[15]=ksm(fac[15],mod-2);
    for(int i=14;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=10;i++) for(int j=1;j<=10;j++) gcd[i][j]=__gcd(i,j);
}
inline ll C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void dfs(int x)
{
    if(x>m)
    {
        int cnt=0;
        for(int i=1;i<m;i++)
            if(gcd[p[i]][p[i+1]]==1) cnt++;
        for(int i=cnt+1,j=0;i<=m;i++,j++) dp[0][i]=(dp[0][i]+C(m-cnt-1,j))%mod;
        return ;
    }
    for(int i=1;i<=m;i++)
    {
        if(vis[i]) continue;
        vis[i]=true;p[x]=i;
        dfs(x+1);
        vis[i]=false;p[x]=0;
    }
}

int main()
{
    freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
    scanf("%d%d",&n,&k);
    init();
    m=n/k;
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        if(i%k==0)
        {
            for(int j=1;j<=n;j++) dp[i][j]=dp[i-1][j];
        }
        else
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i-1][j+1]*j%mod+dp[i-1][j]*2*j%mod+dp[i-1][j-1]*j%mod;
                dp[i][j]%=mod;
            }
        }
    }
    printf("%lld",dp[n][1]);
}