题解：CF2124F1 Appending Permutations (Easy Version)

AC_Lover · 2025-10-17 11:40:10 · 题解

由于是一段一段往后接则自然考虑从前往后 \mathrm{dp}，定义 f_i 表示前 i 个数的方案数，那么我们可以枚举最后一个接上的循环移位 (r,s) 是 [r,r+1,\dots s,1,2,\dots r-1]，判断其是否满足限制，然后从 f_{i-s} 转移过来。但这样做真的正确吗？注意到题目要求我们对本质不同的序列计数，所以需要注意算重的问题，考虑序列 [1,2,3,4,1,2] 会被怎样算到，我们发现其会被 [\underline{1,2},\underline{3,4,1,2}] 和 [\underline{1,2,3,4},\underline{1,2}] 两种拼接方式算到，因此原来的 \mathrm{dp} 算重了。去重考虑刻画出算重的形式，观察发现，如果出现：

这样在计算接上后面的循环移位时会算重，那么我们在 \mathrm{dp} 时多记录一维 j，表示最后接上的这个排列移位是 [1,\dots,j] 的形式，如果不是这个形式则 j=0。转移是简单的。

时间复杂度 O(n^4)。

:::info[代码]

#include <bits/stdc++.h>
#define psb push_back

using namespace std;

typedef long long ll;
const int mod=998244353;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }

const int N=110;
int n;
bool ban[N][N];
int f[N][N];

int main()
{
    int T; cin >> T;
    while (T--)
    {
        int m; cin >> n >> m;
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ban[i][j]=false;
        while (m--) 
        {
            int i,x; cin >> i >> x;
            ban[i][x]=true;
        }
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for (int i=1;i<=n;i++)
        {
            for (int s=0;s<=i;s++)
            {
                for (int r=1;r<=s;r++)
                {
                    bool flag=true;
                    for (int j=i-s+1,x=r;j<=i;j++,x=x%s+1) 
                    {
                        if (ban[j][x])
                        {
                            flag=false;
                            break;
                        }
                    }
                    if (!flag) continue;
                    int len=(r==1) ? s : 0;
                    adm(f[i][len],f[i-s][0]);
                    for (int k=1;k<i;k++) 
                    {
                        if (r!=1 && k==r-1) continue;
                        adm(f[i][len],f[i-s][k]);
                    }
                }
            }
        }

        int ans=0;
        for (int i=0;i<=n;i++) adm(ans,f[n][i]);
        //for (int i=0;i<=n;i++) cout << i << " " << f[n][i] << "\n";
        cout << ans << "\n";
    }

    return 0;
}

:::