1 条题解
-
0
考虑将整个序列通过
.分成 个部分，容易发现，每次操作之后，总有一个部分由初始状态变为全<或者全>。所以最后的序列是形如
<<<<<<====>>>>的，其中=表示和原来相同。然后考虑方案数，令 表示左边 个
.，最后变成全部<的方案数，同理定义 。易得 。
答案就是
$$ans=\frac{\sum_{i=0}^k s_iL_iR_{k-i}C_{k}^{i}}{2^k\times k!} $$这里 表示这种方法的
<数量。考虑求出 。
考虑递推，在最左边新加入一个
.，考虑操作序列。如果它是最后一个操作的，那么它必须向左，否则，它左右都可以，因为会有其他的将它覆盖。
所以
考虑化简上面的式子
$$\frac{\sum_{i=0}^k s_iL_iR_{k-i}C_{k}^{i}}{2^k}=\sum_{i=0}^k s_i(\frac{L_i}{2^i\times i!} \frac{R_{k-i}}{2^{k-i}\times (k-i)!}) $$所以直接令 ，就不需要组合数了。
代码
#include<bits/stdc++.h> using namespace std; const int N=1e5+5,mod=998244353; int n,tot,a[N],sum[N],f[N]; char s[N]; int kuai(int a,int b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod; return ans; } int ans=0; int main(){ scanf("%d%s",&n,s+1); for(int i=1;i<=n;i++){ if(s[i]=='.')tot++,a[tot]=i; sum[i]=sum[i-1]; if(s[i]=='<')sum[i]++; } sum[n+1]=sum[n]; a[tot+1]=n+1,a[0]=0; f[0]=1; for(int i=1;i<=tot;i++)f[i]=1ll*f[i-1]*(2*i-1)%mod*kuai(2*i,mod-2)%mod; for(int i=0;i<=tot;i++)ans=(ans+1ll*f[i]*f[tot-i]%mod*(a[i]+sum[a[i+1]]-sum[a[i]])%mod)%mod; printf("%d",ans); }
- 1
信息
- ID
- 67
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
-
houzhiyuan