题解

思路分析

这是一道结合 数位DP + 状态压缩 + 组合计数 的高难度问题。

问题建模

• 长度为 $n$ 的字符串，只含 I 和 X
• 相邻不同字符的位置数 $\leq k$
• 考虑旋转对称（I $\leftrightarrow$ I，X $\leftrightarrow$ X）
• 求字典序第 $i$ 小的正规表示

核心思路

1. 数位DP计数

定义 $dp[i][j][a][b][e]$ 表示：

• 已确定前 $i$ 个位置
• 已有 $j$ 个相邻不同的位置
• 第1个字符是 $a$（0=I, 1=X）
• 第 $n$ 个字符是 $b$
• 是否已经出现过相邻不同（用于判断对称性）

转移时枚举下一个字符，更新相邻不同的计数。

2. 对称性处理

字符串 $S$ 和其反转 $S'$ 视为同一个石头：

• 如果 $S = S'$（回文），只计数一次
• 如果 $S \neq S'$，取字典序较小的作为正规表示

关键判断：

• 字符串长度为奇数时，中间字符必须与自己对称
• 枚举时需要保证 $S \leq S'$（字典序）

3. 递推构造第i个

从高位到低位枚举：

• 尝试填 I，计算满足条件的方案数
• 如果方案数 $\geq i$，选择 I；否则选择 X，并更新 $i$

4. 边界条件

• 如果 $n$ 为奇数，中间位置需要特殊处理（必须相同）
• 第一个和最后一个字符需要满足对称约束

算法步骤

1. 初始化DP：

   • 对于 $n$ 为奇数，中间位置必须对称
   • 枚举首尾字符，开始DP

2. 递推计数：

   • 从两端向中间填字符
   • 保证字典序约束
   • 累加方案数

3. 构造第i个字符串：

   • 从第1位开始枚举
   • 计算选择 I 的方案数
   • 根据 $i$ 的大小决定选择哪个字符
   • 更新 $i$ 和状态

4. 输出结果

复杂度分析

• 状态数：$O(n \cdot k \cdot 2^3)$
• 转移：$O(2)$（枚举下一个字符）
• 总时间复杂度：$O(n^2 k)$
• 空间复杂度：$O(n \cdot k)$

//test
#include<iostream>
#include<cstring>
#define mem(a,b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 66
#define ll long long
using namespace std;

ll dp[N][N][2][2][2], rnk;
int p[N], n, k;

ll cal(){
    mem(dp, 0);
    if(~p[n]){
        if(p[n] < p[1]) return 0;
        dp[1][0][p[1]][p[n]][p[n]>p[1]] = 1;
    }
    else rep(i,p[1],1) dp[1][0][p[1]][i][i > p[1]] = 1;

    rep(i,1,(n+1)/2-1) rep(j,0,n-1){
        int sa = (~p[i+1] ? p[i+1] : 0), sb = (~p[n-i] ? p[n-i] : 0);
        rep(a,sa, (~p[i+1]?sa:1)) rep(b,sb, (~p[n-i]?sb:1)){
            if((n&1) && i == (n+1)/2-1 && a != b) continue;
            int ex = ((i == (n+1)/2-1) && (a^b));
            rep(c,0,1) rep(d,0,1) rep(e,0,1) if(dp[i][j][c][d][e])
                if(b >= a || e) dp[i+1][j+(a^c)+(b^d)+ex][a][b][e|(b>a)] += dp[i][j][c][d][e];
        }
    }
    ll ans = 0;
    rep(a,0,1) rep(b,0,1) rep(c,0,1) rep(j,0,k)
        ans += dp[(n+1)/2][j][a][b][c];
    return ans;
}

int main(){
    cin>>n>>k>>rnk;
    mem(p, -1);
    rep(i,1,n){
        p[i] = 0;
        ll I = cal();
        if(rnk > I){
            rnk -= I, p[i] = 1;
            ll X = cal();
            if(X < rnk) return puts("NO SUCH STONE"), 0;
        }
    }
    rep(i,1,n) cout<< (p[i] ? 'X' : 'I');
    cout<<endl;
    return 0;
}

题解

我们要按字典序枚举所有长度为 $n$、相邻异字符次数不超过 $k$ 的串，并认为一个串与其反转后相同（180° 旋转）是同一块石头，取两者中字典序较小的一种作为正规表示。为了直接在正规表示序列上做排名，代码使用“逐位构造 + 动态规划”：

1. p[i] 表示第 $i$ 位当前被强制为 I/0 或 X/1，初始全为 -1。主程序按字典序从前往后尝试把第 $i$ 位设为 I，调用 cal() 统计这种前缀下的合法补全个数；若不足以覆盖目标排名，就改设为 X 并相应地扣掉数量。
2. cal() 把串从两端往中间成对地扩展。状态 dp[pos][cnt][L][R][flag] 含义为：已经确定了前 pos 对字符（如果 $n$ 为奇数，中间字符单独处理），累计有 $cnt$ 次相邻异字符，最外层字符分别为 $L$、$R$，flag 表示之前是否已经确定“左边严格小于右边”（保证我们只计入正规表示）。每次选择新的一对字符 $(a,b)$ 时：
   • 如果这一对是中心处且 $a \ne b$，则需要额外计一次变化（因为串与反串不同）。
   • 在没有证明左串严格小于右串之前（flag=0），必须保持 $b \ge a$，否则翻转后的串会更小。
   • 邻位之间是否不同通过 $a \oplus prev$ 累加到 $cnt$ 中。
3. 若 $cnt \le k$ 的终态都会累积到答案里；如果最外层字符已经固定，还要在 DP 开始前检查它们是否满足 $p[n] \ge p[1]$（否则正规表示应该是翻转后的那一侧）。

整套 DP 只依赖于 $n$ 的一半，因此复杂度约为 $O(n^2)$，配合外层的逐位扫描即可在 $n \le 60$ 的范围内完成排名查询；若最终计数仍小于所需排名，就说明不存在对应的石头，输出 NO SUCH STONE。

//test
#include<iostream>
#include<cstring>
#define mem(a,b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 66
#define ll long long
using namespace std;

ll dp[N][N][2][2][2], rnk;
int p[N], n, k;

ll cal(){
    mem(dp, 0);
    if(~p[n]){
        if(p[n] < p[1]) return 0;
        dp[1][0][p[1]][p[n]][p[n]>p[1]] = 1;
    }
    else rep(i,p[1],1) dp[1][0][p[1]][i][i > p[1]] = 1;

    rep(i,1,(n+1)/2-1) rep(j,0,n-1){
        int sa = (~p[i+1] ? p[i+1] : 0), sb = (~p[n-i] ? p[n-i] : 0);
        rep(a,sa, (~p[i+1]?sa:1)) rep(b,sb, (~p[n-i]?sb:1)){
            if((n&1) && i == (n+1)/2-1 && a != b) continue;
            int ex = ((i == (n+1)/2-1) && (a^b));
            rep(c,0,1) rep(d,0,1) rep(e,0,1) if(dp[i][j][c][d][e])
                if(b >= a || e) dp[i+1][j+(a^c)+(b^d)+ex][a][b][e|(b>a)] += dp[i][j][c][d][e];
        }
    }
    ll ans = 0;
    rep(a,0,1) rep(b,0,1) rep(c,0,1) rep(j,0,k)
        ans += dp[(n+1)/2][j][a][b][c];
    return ans;
}

int main(){
    cin>>n>>k>>rnk;
    mem(p, -1);
    rep(i,1,n){
        p[i] = 0;
        ll I = cal();
        if(rnk > I){
            rnk -= I, p[i] = 1;
            ll X = cal();
            if(X < rnk) return puts("NO SUCH STONE"), 0;
        }
    }
    rep(i,1,n) cout<< (p[i] ? 'X' : 'I');
    cout<<endl;
    return 0;
}