ABC234

H. Enumerate Pairs

题意：

给定平面上 \(n\) 个点和参数 \(k\)，找到所有的点对，满足它们的欧几里得距离 \(\le k\)，保证这样的点对最多有 \(4\times 10^5\) 对。

\(n\le 2\times 10^5,k\le 1.5\times 10^9\)。

分析：

这个题很妙。

首先可以 kdt，但是我不会。

考虑暴力一点的想法。一个想法是分块：把平面用 \(k\times k\) 的正方形分成若干块。这样对于一个点，和它距离 \(\le k\) 的点只会存在与它所在块 \(b\) ，还有所有和 \(b\) 的切比雪夫距离等于 \(1\) 的 \(8\) 个块中。

然后对于每个点，暴力和这 \(9\) 个块中的所有点检查是否满足距离 \(\le k\)，就可以通过。

本题最绝妙的就是复杂度分析：

设总共有 \(\Phi\) 对符合条件的点对；

设一个块内有 \(n\) 个点，我们要证明块内符合条件的点对数是 \(n^2\) 级别的。

注意到可以把 \(k\times k\) 的正方形用四个边长为 \(\frac{k\sqrt{2}}{2}\) 的小正方形覆盖掉。而小正方形内任意两点的距离都是小于等于 \(k\) 的。根据鸽笼原理至少有 \(\frac{n}{4}\) 个点会在一个小正方形内。所以一个块内至少有 \(\frac{n^2}{16}\) 级别的符合条件点对。

也就是说对于每个块 \(n^2\) 的暴力，计算量是 \(O(\Phi)\) 的。

考虑对于一个大小为 \(x\) 的块，和一个和它相邻的，大小为 \(y\) 的块，我们会进行 \(xy\) 次判断，而 \(xy\le \frac{x^2+y^2}{2}\)，所以这 \(xy\) 次判断，等价于对两个块分别进行一次 \(n^2\) 暴力。由于一个块只会和 \(8\) 个块进行关连，是一个常数，那么加起来计算量还是 \(O(\Phi)\) 的。

所以总复杂度是 $ O(\Phi)/O(\Phi \log \Phi)$，取决于实现。

代码：

const int MAXN=2e5+10;
ll n,k,x[MAXN],y[MAXN];
map >f;
vector ret;
int ck(int i,int j){
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=k*k;
}
int main(){
    cin>>n>>k;
    rep(i,1,n)cin>>x[i]>>y[i];
    rep(i,1,n){
        pi idx=mp(x[i]/k,y[i]/k);
        rep(a,-1,1)rep(b,-1,1){
            pi flag=mp(idx.fr+a,idx.se+b);
            vectortmp=f[flag];
            for(auto p:tmp){
                if(ck(p,i)){
                    ret.pb(mp(p,i));
                }
            }
            
        }
        f[idx].pb(i);
    }
    sort(ret.begin(),ret.end());
    printf("%u\n",ret.size());
    for(auto p:ret)printf("%d %d\n",p.fr,p.se);
    return 0;
}

ABC235

G. Gardens

题意：

给定 \(n\) 个盒子，\(A\) 个红球，\(B\) 个黄球，\(C\) 个蓝球，相同颜色的球之间没有差别，不同的盒子有差别。

需要把球放置在盒子里，使得：

• 每个盒子非空
• 一个盒子里不能有相同颜色的球

注意不一定要放完所有的球。

问放置方式对 \(998244353\) 取模的结果。

\(n\le 5\times 10^6,A,B,C\le n\)。

分析：

被我场上二十分钟过的题，想来大家都会了吧。

考虑去掉第一个限制的情况。

注意到三种颜色的球独立。对于红球，枚举它最后使用的个数 \(0\le x\le A\)，那么红球的总放置方案是 \(\sum_{x=0}^A \dbinom{n}{x}\)。

黄球，蓝球同理，相乘即可。

此时加入第一个限制：考虑二项式反演：设 \(f(x)\) 表示至多 \(x\) 个盒子非空的方案数，\(g(x)\) 是恰好 \(x\) 个盒子非空的方案数，我们要求的是 \(g(n)\)。容易发现：

那么根据二项式反演得：

本题求 \(g(n)\) 就是 \(\sum_{i=0}^{n}(-1)^{n-i}\dbinom{n}{i}f(i)\)。

发现瓶颈在于求 \(f(i)\)，开始讲过了 \(f(i)=(\sum_{x=0}^A \dbinom{i}{x})(\sum_{y=0}^B \dbinom{i}{y})(\sum_{z=0}^C \dbinom{i}{z})\)。

但是这样单次求 \(f(n)\) 是 \(n^2\) 的。发现这个下标是一个下指标变化的求和，而我们一般都是做上指标变化的求和，也不方便搞。

确实，我们很难为这个式子找出一个通项。但是我们可以递推！

设 \(S_n=\sum_{x=0}^{A}\dbinom{n}{x}\)，我们考虑从 \(S_n\) 推出 \(S_{n+1}\)。

由于 \(\dbinom{n+1}{x}=\dbinom{n}{x}+\dbinom{n}{x-1}\)。所以我们不难推出：\(S_{n+1}=2\times S_n - \dbinom{n}{A}\)。

这样对于红色球就可以 \(O(n)\) 预处理了。

黄蓝球亦然。时间复杂度 \(O(n)\)。

代码：

const int MAXN=5e6+10,mod=998244353,LIM=5e6+5;
ll power(ll a,ll n){
    if(!n)return 1;
    ll tmp=power(a,n/2);tmp=tmp*tmp%mod;
    if(n&1)tmp=tmp*a%mod;return tmp;
}
ll n,a,b,c;
ll fact[MAXN],inv[MAXN];
ll sa[MAXN],sb[MAXN],sc[MAXN];
ll C(ll n,ll m){
    if(n<0 || m<0 || n>n>>a>>b>>c;
    sa[0]=sb[0]=sc[0]=1;
    rep(i,1,n){
        sa[i]=2*sa[i-1]%mod;
        sa[i]=(sa[i]-C(i-1,a)%mod+mod)%mod;
        sb[i]=2*sb[i-1]%mod;
        sb[i]=(sb[i]-C(i-1,b)%mod+mod)%mod;
        sc[i]=2*sc[i-1]%mod;
        sc[i]=(sc[i]-C(i-1,c)%mod+mod)%mod;
    }
    printf("%lld",G(n));
    return 0;
}

H. Painting Weighted Graph（推荐）

题意：

给定一张 \(n\) 点 \(m\) 边带权无向图 \(G\)，开始所有点是黑色的。

称点 \(u\) 和点 \(v\) 是 ”\(x\) 可达的“，当且仅当图上存在一条从 \(u\) 到 \(v\) 的路径，满足路径上边权不超过 \(x\)。

你可以进行至多 \(k\) 次操作：任选一个点 \(u\) 和参数 \(x\)，把所有和 \(u\) 是 "\(x\) 可达" 的点 \(v\) 都涂成红色（包括点 \(u\) 本身）。

求最后的图多少种颜色。两张图颜色不同，当且仅当存在一个点，在一张图是黑的，另一张图是红的，对 \(998244353\) 取模。

\(n,m\le 10^5,k\le 500\)。

分析：

Part. 1

这个 \(x\) 可达容易让我们想到建重构树。然后一次操作就等价于把子树的点全部染红。

但是想一想，不是所有子树都可以选择的。如果一个点的权值和它的父亲权值一样，那这个点就不能操作。

为了避免这种麻烦（虽然最后这样也能做），我们来魔改一下重构树：

每次加入一种权值 \(w\) 的边后，我们会剩下几个连通块，对于一个连通块，我们把加入 \(w\) 条边的两端点的父亲都设成一个点。

举个简单的例子：

如果 \(1\leftrightarrow 2\leftrightarrow 3\)，边权都为 \(1\)。传统的重构树会搞出 \(1\) 和 \(2\) 的父亲是 \(4\)，\(4\) 和 \(3\) 的父亲是 \(5\)（\(4,5\) 是重构树搞出来的虚点），但我们这里的重构树是 \(1,2,3\) 的父亲都为 \(4\)）。

如果这个时候还有 \(4\leftrightarrow 5\leftrightarrow 6\) 了，那么就是 \(1,2,3\) 的父亲都为 \(7\)，\(4,5,6\) 的父亲都为 \(8\) 这样。

这个实现不是很难。

由于没保证最后是连通的，所以可以建个虚点 \(0\) 把重构森林变成重构树，只不过记得这个虚根不能操作。

然后就变成了树上操作：每次选定一个节点（可以是叶子）操作一次，把子树内所有的叶子染红。此时就方便考虑了。

Part. 2

首先要明白一个事情：我们只关注每个叶子的染色状态，不关注非叶子节点的染色状态。因为重构树上的叶子节点才是原图中的点。

容易想到设计一个 \(O(nk)\) 的树形 \(dp\)。然后你发现这个 \(dp\) 的状态设计是有讲究的。因为本题求的是至多 \(k\) 次操作，势必有些状态有多种方案可以达到。比如说如果是“所有点都红色”这个状态，可以对根节点直接进行一次操作，也可以对根节点的所有儿子进行操作，效果一样。

所以设 \(f(i,j)\) 是 \(i\) 为根的子树，有多少种叶子结点的状态，是最少 \(j\) 步可以完成的。

最终答案是 \(\sum_{i=0}^{k} f(0,i)\)。

发现转移是个类似背包的东西，就是每次节点 \(u\) 遍历到一个新的儿子 \(v\)，然后 \(f'(u,x+y)+=f(u,x)f(v,y)\) 这样的转移。众所周知，这个转移的复杂度是看上去 \(O(nk^2)\) 实际上 \(O(nk)\) 的。但是存在一些细节：

• \(0\) 节点特判，不能染色
• 对于非 \(0\) （也不是叶子）的节点，注意到如果我们不对根节点进行操作，那么开始初始化 \(f(u,0)=1\)，然后执行上述背包转移即可。如果我们对根节点进行操作了，那么”子树里所有点都为红色“这个状态的最少步数是 \(1\)，所以 \(f(u,1)\) 加一。但是在之前，这个状态的最少步数是 \(u\) 的儿子个数 \(son\)，所以 \(f(u,son)\) 减一。

时间复杂度 \(O(nk)\)。

代码：

const int MAXN=1e5+10,MAXM=510,mod=998244353;
int n,m,k,tot;
int f[MAXN*2],vis[MAXN*2];
int dp[MAXN*2][MAXM],tmp[MAXM],sz[MAXN*2];
struct Edge{
    int u,v,w;
    bool operator<(const Edge& e2)const{return wt[MAXN*2],son[MAXN*2];
settag;
void dfs(int u){
    vis[u]=1;
    son[tot].pb(u);
    f[u]=tot;
    for(int v:t[u]){
        if(vis[v])continue;
        dfs(v);
    }
}
void build(int l,int r){
    tag.clear();
    rep(i,l,r){
        t[Find(e[i].u)].clear();
        t[Find(e[i].v)].clear();
        tag.is(Find(e[i].u));
        tag.is(Find(e[i].v));
        vis[Find(e[i].u)]=vis[Find(e[i].v)]=0;
    }
    rep(i,l,r){
        if(Find(e[i].u)==Find(e[i].v))continue;
        t[Find(e[i].u)].pb(Find(e[i].v));
        t[Find(e[i].v)].pb(Find(e[i].u));
    }
    for(int u:tag){
        if(vis[u])continue;
        if(t[u].empty())continue;
        tot++;f[tot]=tot;
        dfs(u);
    }
}
void dfs2(int u){
    sz[u]=1;dp[u][0]=1;
    for(int v:son[u]){
        dfs2(v);
        rep(i,0,k)tmp[i]=0;
        rep(i,0,min(k,sz[u]))rep(j,0,min(k-i,sz[v])){
            tmp[i+j]=(tmp[i+j]+1ll*dp[u][i]*dp[v][j])%mod;
        }
        rep(i,0,k)dp[u][i]=tmp[i];
        sz[u]+=sz[v];
    }
    if(u){dp[u][1]=(dp[u][1]+1)%mod;}
    int cnt=son[u].size();
    if(u && cnt>0 && cnt<=k){
        dp[u][cnt]=(dp[u][cnt]+mod-1)%mod;
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);tot=n;
    rep(i,1,m){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);}
    sort(e+1,e+1+m);
    rep(i,1,n)f[i]=i;
    //build tree
    for(int l=1,r;l<=m;l=r+1){
        r=l;
        while(e[r+1].w==e[r].w)r++;
        build(l,r);
    }
    rep(i,1,tot){if(Find(i)!=i)continue;son[0].pb(i);}
    dfs2(0);
    int ans=0;rep(i,0,k)ans=(ans+dp[0][i])%mod;
    printf("%d",ans);
    return 0;
}

ABC236

G. Good Vertices

题意：

给定一张 \(n\) 点有向图，初始没有边。接下来进行 \(m\) 次加边操作。（允许自环）

称一个点 \(i\) 是好的，当且仅当存在一条长度恰好为 \(L\) 的，从 \(1\) 到 \(i\) 的路径。

对于每个点，求出从加入第几条边开始，它是好的。

\(n\le 100,m\le n^2,L\le 10^9\)。

分析：

看上去很像矩阵快速幂的模板，但是我们不好直接做。

我们很难每次加边就查看哪些点成为了好点。而且也没有在线询问我们。所以不妨离线这个问题：给每条边赋上一个边权，边权为它被加入的时间。

这样，对于每个点 \(u\) 就是找到一个最小的 \(i\)，满足 \(1\rightarrow u\) 存在一条长度恰好为 \(L\) 的，路径上最大值不超过 \(i\) 的路径。

这个长度恰好为 \(L\)，一看就是矩阵快速幂优化，说人话就是朴素的 \(dp\) 设计里要带上这一维”当前经过的边数“。

考虑设 \(dp(i,j)\)，\(i\) 是走了几步，\(j\) 是走到的点，代表这个状态下，路径上最大值的最小可能，初始只有 \(dp(0,1)=0\)。

那么转移，有 \(dp(i,j)=\min\{\max\{dp(i-1,k),w_{k,j}\}\}\)。

发现这个转移方式不管 \(i\) 是多少都是不变的，而且 \(i\) 又很大，那么上矩阵快速幂优化就好了，时间复杂度 \(O(n^3\log L)\)。

注：

我们经常会碰到一些类似形式的转移，长得很像矩阵乘法但是不清楚能不能矩阵快速幂优化。AtCoder 在官方题解中给出了能运用矩阵快速幂的充要条件：

如果有转移 \(f(i,j)=\sum g(i,k)h(k,j)\)，这里 \(+\) 和 \(\times\) 必须满足的运算性质：

• 加法是可交换幺半群（注意不要求有逆元）。
• 乘法是幺半群。
• 乘法有零元.
• 两种分配律成立：\((a+b)\times c=a\times c+b\times c\) 以及 \(a\times (b+c)=a\times b+a\times c\)。

事实上这个性质还算是自然的，也不难记忆。

代码：

const int MAXN=110,INF=1e9;
int n,m,l;
int g[MAXN][MAXN];
struct Matrix{
    int val[MAXN][MAXN],n,m;
    void operator=(const Matrix& m2){
        n=m2.n,m=m2.m;
        rep(i,1,n)rep(j,1,m)val[i][j]=m2.val[i][j];
    } 
    Matrix operator*(const Matrix& m2)const{
        Matrix ret;ret.n=n,ret.m=m2.m;
        rep(i,1,ret.n)rep(j,1,ret.m){
            ret.val[i][j]=INF;
            rep(k,1,m){
                ret.val[i][j]=min(ret.val[i][j],max(val[i][k],m2.val[k][j]));
            }
        }
        return ret;
    }
    Matrix mypow(int n)const{
        if(n==1)return (*this);
        Matrix tmp=mypow(n/2);
        tmp=tmp*tmp;
        if(n&1)tmp=tmp*(*this);
        return tmp;
    }
}f,A;
int main(){
    cin>>n>>m>>l;
    rep(i,1,n)rep(j,1,n)g[i][j]=INF; 
    rep(i,1,m){
        int u,v;cin>>u>>v;
        g[u][v]=i;
    }
    f.n=1,f.m=n;
    A.n=A.m=n;
    rep(i,1,n)rep(j,1,n)A.val[i][j]=g[i][j];
    rep(i,2,n)f.val[1][i]=INF;
    f=f*A.mypow(l);
    rep(i,1,n){
        if(f.val[1][i]==INF)printf("%d ",-1);
        else printf("%d ",f.val[1][i]);
    }
    return 0;
}

H. Distinct Multiples（推荐）

题意：

给定长度为 \(n\) 的序列 \(d_1,d_2,...,d_n\)，对符合条件的 \(a_1,a_2,...,a_n\) 计数：

• \(1\le a_i\le m\)。
• \(a_i\neq a_j(i\neq j)\)
• \(d_i\mid a_i\)。

答案对 \(998244353\) 取模。

\(n\le 16,1\le d_i\le m\le 10^{18}\)。

分析：

个人认为是本篇8场比赛里质量最高的一道（事实上我认为236H,238H,235H是所有题目中质量最高的三道），值得反复品味。

碰到这种多条件，每个条件都看上去比较简单的计数容易想到容斥。对这三个条件做容斥，基本都会选择容斥掉条件 \(2\)：因为 \(1,3\) 条件的结合是自然的。

那这个 \(2\) 条件，很容易让我们想到转成无向图连边。先不谈这个，从组合角度入手，设条件 \(A_{i,j}\) 代表 \(a_{i}=a_{j}(i ，那么我们要求的是 \(\mid \overline{A_{1,2}} \cap \overline{A_{1,3}} \cap ... \cap ... \overline{A_{n-1,n}}\mid\) 。根据容斥原理，我们设 \(f(S)\) 是集合 \(S\) 里的条件都满足的方案数，答案是 \(\sum (-1)^{|S|}f(S)\)。

但是条件有 \(n^2\) 级别个，直接状压啥的是瞎扯淡。

那么把条件 \(A_{i,j}\) 看作一条 \(i\leftrightarrow j\) 的边，它成立就对应无向图上这条边出现的情况。如果我们能对点集做一个统计就好了。

我们现在只有一个很模糊的思路：设 \(dp(V)\) 代表点集 \(V\) 里的点，所有情况（就是点集 \(V\) 中每条边出现或者不出现都会分两种情况考虑）的 \((-1)^{|S|}\) 总和（\(S\) 是当前情况下的所有出现的边构成的集合），那么 \(dp(\{1,2,...,n\})\) 就是答案。

考虑划分连通块进行 \(dp\)，就是枚举 \(T\subset S\)，强制 \(T\) 中所有点连通，设这个贡献（注意这里贡献是啥也不清楚，只是一个思路）\(g(T)\)，那么转移就是 \(dp(S)\) 加上 \(g(T)dp(S-T)\)。

那么第一个问题是考虑去重，一个经典套路是强制 \(T\) 包含 \(S\) 的最低位。

第二个问题是 \(g\) 到底是什么玩意。注意到一个事情就是 \((-1)^{x}\) 是有良好运算性质的：一个边集 \(S\) 的 \((-1)^{|S|}\)，可以从图上看，把它拆成若干个连通块，设第 \(i\) 个连通块有 \(k_i\) 条边，那么 \(\prod (-1)^{k_i}=(-1)^{|S|}\)。

所以 \(g(T)\) 的定义是这样的：对于每一种让点集 \(T\) 连通的方式，如果边数为偶数加上 \(1\)，否则加上 \(-1\)（开始为 \(0\)）。

如果能算 \(g(T)\)，就能知道答案。

首先设 \(G\) 是 \(T\) 中的点的 \(d\) 的 \(lcm\)，那么取值一共有 \(\left\lceil\frac{M}{lcm}\right\rceil\) 种（所以转移的时候实际上是 \(g(T)dp(S-T)\) 还要乘上这个东西）。对于每一种，我们要进行上面的计数。

注意此时的计数只和 \(T\) 的点数有关。具体来说是 \(g(T)=(-1)^{|T|-1}(|T|-1)!\)（就是阶乘）。

这个 \(g\) 的确定非常牛逼（以下 \(g(x)\) 是指点数为 \(x\) 的集合的答案，换种说法，容斥系数）：

\(g(1)=1\) 这是显然的。

考虑 \(x\gt 1\) 的情况。连通块相关的一个方法是容斥：我从所有可能情况里去掉不连通的情况。首先，所有情况的 \(1/-1\) 的和是 \(0\)，因为选偶数条边的方案数等于选奇数条边的方案数。然后考虑容斥：去掉不全联通的情况的贡献。为了去重设 \(T\) 为第一个点所在的集合，而 \(S\) 是 \(x\) 个点里 \(T\) 的补集。那么此时的和是 \(T\) 内部连通的 \(-1/1\) 之和 $\times $ \(S\) 内部的边随便选的 \(-1/1\) 之和。当 \(|S|>1\) 的时候显然第二个乘数为 \(0\) 所以我们忽略它。那么只用考虑 \(|S|=1\) 的情况，这个点有 \((x-1)\) 种选择，那么 \(g(x)=-(x-1)g(x-1)\)，加上 \(g(1)=1\) 的初始条件，可以推导出通项。

时间复杂度 \(O(3^n)\)，听说最后有啥高科技还可以加速这个过程。

代码：

const int MAXN=20,MAXM=(1<<20),mod=998244353;
ll n,m,d[MAXN],fact[MAXN];
ll g[MAXM],dp[MAXM],pcnt[MAXM];
ll H(int n){
	if(even((n-1)))return fact[n-1];
	else return (mod-fact[n-1]);
}
ll gcd(ll a,ll b){
	if(!b)return a;
	return gcd(b,a%b);
}
int main(){
	fact[0]=1;rep(i,1,19)fact[i]=fact[i-1]*i%mod;
	cin>>n>>m;
	rep(i,1,(1<>d[i];
	rep(i,0,n-1)g[1<b){
			g[i]=-1;
		}else{
			g[i]=v1/d*v2;
		}
	}	
	rep(i,1,(1<

const int MAXN=210,MAXM=(MAXN*2)*(MAXN*2)*2,base=13331,INF=1e9;
int n,f[MAXN][MAXN],tot;
char s[MAXN];
ull h[MAXN],power[MAXN];
arraytmps[MAXN*2];
ull qry(int l,int r){return h[r]-h[l-1]*power[r-l+1];}
int check(int x,int y){
    int m=tmps[y][1]-tmps[y][0]+1;
    rep(i,tmps[x][0],tmps[x][1]-m+1)if(qry(i,i+m-1)==qry(tmps[y][0],tmps[y][1]))return 1;
    return 0;
}
void add(int x,int y){
    rep(i,1,tot)if(qry(x,y)==qry(tmps[i][0],tmps[i][1]))return;
    tmps[++tot]={x,y};
}
namespace G{
    int n,s,t;
    int fst[MAXN*2],nxt[MAXM],tot;
    int dis[MAXN*2],cur[MAXN*2];
    queueq;
    struct E{int u,v,c,f;}edge[MAXM];
    void adde(int u,int v,int c){edge[++tot]=(E){u,v,c,0};nxt[tot]=fst[u];fst[u]=tot;}
    void link(int u,int v,int c){adde(u,v,c);adde(v,u,0);}
    void build(int tot){
        n=tot;s=n*2+1,t=s+1;
        rep(i,1,n)rep(j,1,n)if(i!=j){
            if(check(i,j))link(i,j+n,1);
        }
        rep(i,1,n)link(s,i,1),link(i+n,t,1);
    }
    int bfs(){
        rep(i,1,t)dis[i]=INF;dis[s]=0;q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int j=fst[u];j;j=nxt[j]){
                if(edge[j].f==edge[j].c)continue;
                int v=edge[j].v;
                if(dis[v]>dis[u]+1){
                    dis[v]=dis[u]+1;q.push(v);
                }
            }
        }
        return dis[t]!=INF;
    }
    int dfs(int u,int f){
        if(u==t || !f)return f;
        int ret=0;
        for(int& j=cur[u];j;j=nxt[j]){
            int v=edge[j].v;if(dis[v]!=dis[u]+1)continue;
            int val=dfs(v,min(f,edge[j].c-edge[j].f));
            ret+=val;edge[j].f+=val;
            f-=val;edge[op(j)].f-=val;
            if(!f)break;
        }
        return ret;
    }
    int dinic(){
        int ret=0;
        while(bfs()){
            rep(i,1,t)cur[i]=fst[i];
            ret+=dfs(s,INF);
        }
        return ret;
    }
};
int main(){
    power[0]=1;rep(i,1,200)power[i]=power[i-1]*base;
    ios::sync_with_stdio(false);
    cin>>(s+1);n=strlen(s+1);
    rep(i,1,n)f[i][i-1]=f[i][i]=1,h[i]=h[i-1]*base+(s[i]-'a'+1);
    rep(len,2,n)rep(i,1,n){
        int j=i+len-1;if(j>n)break;
        f[i][j]=(s[i]==s[j])&f[i+1][j-1];
    }
    rep(i,1,n){
        rep(d,0,n){
            if(i-d<1||i+d>n)break;
            if(f[i-d][i+d])add(i-d,i+d);
        }
        if(i==n)break;
        rep(d,0,n){
            if(i-d<1||i+d+1>n)break;
            if(f[i-d][i+d+1])add(i-d,i+d+1);
        }
    }
    G::build(tot);
    cout<

const int MAXN=310,mod=998244353;
ll mypow(ll a,ll n){if(!n)return 1;ll tmp=mypow(a,n/2);tmp=tmp*tmp%mod;if(n&1)tmp=tmp*a%mod;return tmp;}
ll n,c[MAXN][MAXN],fact[MAXN],inv[MAXN];
ll f[MAXN][MAXN],g[MAXN][MAXN],ans;
char s[MAXN];
void upd(ll& x,ll y){x=(x+y)%mod;}
void dp(){
    rep(i,0,n-1)f[i][(i+1)%n]=1;
    rep(len,2,n){
        rep(i,0,n-1){
            int j=(i+len)%n;
            int k=(i+1)%n,cnt=0;
            while(k!=j){
                ll c1=(s[i]=='R')+(s[j]=='L');
                ll c2=(s[i]=='R')*(k>i?k-i:k-i+n)+(s[j]=='L')*(j>k?j-k:j-k+n);
                upd(f[i][j],c1*f[i][k]%mod*f[k][j]%mod*c[len-2][cnt]%mod);
                upd(g[i][j],c2*f[i][k]%mod*f[k][j]%mod*c[len-2][cnt]%mod);
                upd(g[i][j],c1*g[i][k]%mod*f[k][j]%mod*c[len-2][cnt]%mod);
                upd(g[i][j],c1*f[i][k]%mod*g[k][j]%mod*c[len-2][cnt]%mod);
                k=(k+1)%n;cnt++;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>s;
    c[0][0]=1;rep(i,1,300){c[i][0]=1;rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}
    fact[0]=inv[0]=1;rep(i,1,300)fact[i]=fact[i-1]*i%mod,inv[i]=mypow(fact[i],mod-2);
    dp();
    rep(i,0,n-1)upd(ans,g[i][i]);
    ans=ans*inv[n]%mod;cout<