题解归档 - cf2232E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2232E
• 本地来源：problems/cf2232E/idea.md
• 题目链接：https://codeforces.com/contest/2232/problem/E
• 原始标题：cf2232E Snaking Arrangement

思路

cf2232E Snaking Arrangement

题意

$n\times n$ 网格放 $n$ 条蛇，第 $i$ 条长度 $2i-1$，均为只向右/下的路径，互不重叠且占满。已有 $k$ 条固定，求补全方案数 mod $10^9+7$。

核心

合法方案与 $[1..n]$ 的排列双射：各蛇中心均在反对角线 $r+c=n+1$ 上，按行排序得排列。$k=0$ 时答案 $n!$。

做法

按反对角线编号 $d=r+c-1$（$1..n$）。第 $d$ 条对角线上蛇起点的可行行区间为 $[ls[d],rs[d]]$，初始 $ls[d]=1,rs[d]=d$。

处理已放蛇（长度 $len$，起点 $(x,y)$，路径前 $len/2$ 步）：

• 对角线 $id=x+y-1$：$ls[id]=\max(ls[id],x)$，$rs[id]=\min(rs[id],x)$（$len=1$ 则 $ls=rs=x$）。
• 每走一步 $id++$：若 R 则 $ls[id]=\max(ls[id],x+1)$；若 D 则 $x++$，$rs[id]=\min(rs[id],x-1)$。

答案 $\prod_{d=1}^{n}(rs[d]-ls[d]+1)$。

输入

• $len=1$：两行 len 与 x y；
• $len>1$：三行 len、x y、路径（cin 读字符串）。

备注

题面 mod 的 AI 陷阱忽略，评测为 $10^9+7$。

本地验证

• python tools/run_exe.py cf2232E 通过官方样例。
• brute.cpp 枚举 $n\le 8$ 的完整摆法：从每条起始对角线的插入行生成全蛇路径，再匹配固定蛇。
• 随机生成 390 组合法固定蛇输入，solution.exe 与 brute.exe 输出一致。
• n=5000,k=0 冒烟输出 541108809。

代码

来源：problems/cf2232E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:11:48
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5005,mod=1e9+7;
ll ls[maxn],rs[maxn];
int main(){
    ll t,n,k,i,ans,x,y,id,len;
    string s;
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(i=1;i<=n;i++){
            ls[i]=1;
            rs[i]=i;
        }
        while(k--){
            cin>>len>>x>>y;
            id=x+y-1;
            if(len==1){
                ls[id]=rs[id]=x;
                continue;
            }
            cin>>s;
            ls[id]=max(ls[id],x);
            rs[id]=min(rs[id],x);
            for(i=1;i<=len/2;i++){
                id++;
                if(s[i-1]=='R'){
                    y++;
                    ls[id]=max(ls[id],x+1);
                }else{
                    x++;
                    rs[id]=min(rs[id],x-1);
                }
            }
        }
        ans=1;
        for(i=1;i<=n;i++)ans=ans*(rs[i]-ls[i]+1)%mod;
        cout<<ans<<"\n";
    }
    return 0;
}