首页 > 其他分享 >Atcoder ARC132E Paw

Atcoder ARC132E Paw

时间:2024-03-21 21:57:02浏览次数:38  
标签:Atcoder 右边 ARC132E Paw int 左边 inv i64 maxn

考虑最后往左走往右走的覆盖情况。
能发现肯定是有两个洞之间,或者是第一个洞左边,最后一个洞右边没有被覆盖,而左边的都被覆盖为向左,右边的都被覆盖为向右。
大致证明就是考虑左边这一部分,如果有向右的,那么其右边的洞肯定都需要走过才行,不然会被覆盖,那么这样就可以一次性走出左边,就不合法了,右边同理。

于是考虑设 \(f_i\) 为一边有 \(i\) 个洞的概率。
假设为左边来考虑,右边同理。
如果选到了最靠右的,其就只能向左边走,否则没有要求,就有 \(f_i = f_{i - 1}\times (1 - \frac{1}{2n})\)。

那么令一共有 \(p\) 个 .,第 \(i\) 个 . 的位置是 \(w_i\)。
选到了第 \(i\) 和 \(i + 1\) 个洞,概率就是 \(f_i\times f_{p - i}\),对应的数量就是 \(w_i + \operatorname{count}(w_i + 1, w_{i + 1} - 1)\),\(\operatorname{count}(l, r)\) 代表 \([l, r]\) 中 ( 的个数。

对于每种选取都选一遍求和即可。

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

代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
const int maxn = 2e5 + 10;
i64 inv[maxn], f[maxn];
char s[maxn];
int sum[maxn];
int main() {
    int n; scanf("%d%s", &n, s + 1);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= (n << 1); i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (mod + 1 - inv[i << 1]) % mod;
    std::vector<int> w; int cnt = 0;
    w.push_back(0);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '<'), s[i] == '.' && (w.push_back(i), cnt++);
    w.push_back(n + 1);
    i64 ans = 0;
    for (int i = 0; i + 1 < w.size(); i++) {
        i64 p = f[i] * f[cnt - i] % mod;
        (ans += p * (sum[w[i + 1] - 1] - sum[w[i]] + w[i])) %= mod;
    }
    printf("%lld\n", ans);
    return 0;
}

标签:Atcoder,右边,ARC132E,Paw,int,左边,inv,i64,maxn
From: https://www.cnblogs.com/rizynvu/p/18088315

相关文章

  • Atcoder ARC140D One to One
    考虑到对于\(n\)个点的连通块,那就有\(n\)条边,就是个基环树。如果这里面有\(1\)个\(-1\),那么就是\(n-1\)条边,就是一棵树。如果有\(2\)个\(-1\),\(n-2\)条边一定不连通,不可能出现。令\(-1\)的个数为\(c\)。那么先对于已知的边连上,如果一个连通块是基环树就直......
  • AtCoder Beginner Contest 345
    A-Leftrightarrow(abc345A)题目大意给定一个字符串,问是不是形如<======...====>的字符串。解题思路根据长度构造出期望的字符串,再判断是否相等即可。神奇的代码s=input()print("Yes"ifs=="<"+"="*(len(s)-2)+">"else"No")B-Inte......
  • AtCoder Beginner Contest 345
    A-Leftrightarrow#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingldb=longdouble;#defineintlonglongusingvi=vector<int>;usingpii=pair<int,int>;constintmod=1e9+7;......
  • AtCoder Beginner Contest 345 A-F 题解
    A-LeftrightarrowQuestion给你一个由<、=和>组成的字符串\(S\)。请判断\(S\)是否是双向箭头字符串。字符串\(S\)是双向箭头字符串,当且仅当存在一个正整数\(k\),使得\(S\)是一个<、\(k\)个=和一个>的连接,且顺序如此,长度为\((k+2)\)。Solution按照题意......
  • Atcoder ARC165D Xor Sum 5
    考虑到这个最终的答案是\(\oplus\),所以只需要考虑每种排列出现的次数的奇偶,如果为奇再计算贡献即可。考虑什么情况下出现次数为奇。令每个数出现的个数为\(c_{1\simn}\),方案数即为\(\dbinom{k}{c_1,c_2,\cdots,c_n}=\prod_{i=1}^n\dbinom{k-\sum\limits_{j=1}^{......
  • Monoxer Programming Contest 2024(AtCoder Beginner Contest 345)
    MonoxerProgrammingContest2024(AtCoderBeginnerContest345)\(A\)Leftrightarrow\(100pts\)按照题意模拟即可。点击查看代码intmain(){strings;inta=0,b=0,c=0,i;cin>>s;for(i=0;i<s.size();i++){a+=(s[i]=='<&#......
  • AtCoder-abc345_f题解
    题意简述给定一个无向图。你要在其中选出一些边,使得选出的边所构成的图中,度数为奇数的点有\(K\)个。如果可以,输出选了哪些边,否则输出-1。思路首先在选一条边时,边两端点度数的奇偶性一定都会改变,即要么都变为奇数,要么两个点的奇偶性交换过来,要么都变为偶数。这三种情况时满足......
  • AtCoder Beginner Contest 345
    是这样的,C的longlong只开了ans没开全局,AC12WA12,调了一个小时,在赛后1min发现了该错误。没开longlong见祖宗,望周知;这是C的码,简单的小题一只,可怜的longlong。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;strings;intn,f,ans;map<char......
  • AtCoder Grand Contest 022 E Median Replace
    洛谷传送门AtCoder传送门考虑对于一个确定的串怎么判断合法性。容易发现删到某个时刻若\(1\)的个数大于\(0\)的个数了,因为我们肯定不会蠢到在不是全\(1\)的时候删\(111\),所以\(c_1-c_0\)在不是全\(1\)的时候至少是不会变小的。所以我们的目标就是让\(c_1-c_0......
  • AtCoder Beginner Contest 344 A-G 题解
    AtCoderBeginnerContest344A-SpoilerQuestion删除两个|之间的字符Solution按照题意模拟即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){strings;cin>>s;stringp1,p2;for(inti=0;i<s.size();i++){......