哪个网站可以领单做效果图,时事新闻热点摘抄,泰安网站建设dxkjw,做婚恋网站赚钱吗CF785D Anton and School - 2
题意#xff1a;
给定一个长度≤210^5由(和)组成的字符串#xff0c;问有多少个子串#xff08;可以不连续#xff09;#xff0c;前半部分是由(组成后半部分由)组成.
题解#xff1a;
怎么括号匹配能出这么多题 如何才能不重不漏的选出…CF785D Anton and School - 2
题意
给定一个长度≤2×10^5由(和)组成的字符串问有多少个子串可以不连续前半部分是由(组成后半部分由)组成.
题解
怎么括号匹配能出这么多题 如何才能不重不漏的选出所有括号呢
枚举每个位置的i时我们通过i左括号数量和右括号的数量可以算出当i为最后一个左括号时满足条件的子序列数量。这样统计括号数量不会重不会漏。(第i位是右括号的情况都会被包含其中不会漏)
我们设左边有a个左括号(包括自己)右边有b个右括号满足条件的字串有Ca−10Cb1Ca−11Cb2...Ca−1xCbx1...∑i0min(a−1,b−1)Ca−1xCbx1C_{a-1}^{0}C_{b}^{1}C_{a-1}^{1}C_{b}^{2}...C_{a-1}^{x}C_{b}^{x1}...\sum_{i0}^{min(a-1,b-1)}C_{a-1}^{x}C_{b}^{x1}Ca−10Cb1Ca−11Cb2...Ca−1xCbx1...i0∑min(a−1,b−1)Ca−1xCbx1 从左侧a-1个左括号中选x个还有第i位本身这个左括号再从右侧b个右括号中选x1个组成一个合法的括号序列 然后怎么做 暑假多校的时候学到一个东西范德蒙德卷积我经常当做组合数的定理来记。 ∑i0kCniCmk−iCnmk\sum_{i0}^{k}C_{n}^{i}C_{m}^{k-i}C_{nm}^{k}i0∑kCniCmk−iCnmk 严谨的证明可以用二项式定理证得,具体证明我也不知道不过其中的含义挺好理解在n物品中取i个m个物品中k-i个就是在nm个物品中取k个 回到本题上 我们现在有∑i0min(a−1,b−1)Ca−1xCbx1∑i0min(a−1,b−1)Ca−1a−1−xCbx1Cab−1a\sum_{i0}^{min(a-1,b-1)}C_{a-1}^{x}C_{b}^{x1}\sum_{i0}^{min(a-1,b-1)}C_{a-1}^{a-1-x}C_{b}^{x1}C_{ab-1}^{a}∑i0min(a−1,b−1)Ca−1xCbx1∑i0min(a−1,b−1)Ca−1a−1−xCbx1Cab−1a 这一下子不久好做多了然后从第一位开始枚举如果是左括号就计算这个组合数记录答案
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
const int mod 1e9 7;
ll poww(ll a, ll b)
{ll ans 1;while (b) {if (b 1)ans ans * a % mod;a a * a % mod;b 1;}return ans % mod;
}
ll fac[maxn], inv[maxn];
void init(int N)
{fac[1] 1;for (int i 2; i N; i) {fac[i] (fac[i - 1] * i) % mod;}inv[N] poww(fac[N], mod - 2) % mod;// cout inv[N] endl;for (int i N - 1; i 0; i--) {inv[i] inv[i 1] * (i 1) % mod;}
}
int R[maxn];
ll C(ll a, ll b)
{if (a b || a 0 || b 0)return 0;// cout (fac[a] % mod * (inv[b] % mod)) % mod * (inv[a - b] % mod) % mod endl;return (fac[a] % mod * (inv[b] % mod)) % mod * (inv[a - b] % mod) % mod;
}
int main()
{//rd_test();init(200000);string s;cin s;int len s.length();for (int i len - 1; i 0; i--) {R[i] R[i 1] ((s[i] )) ? 1 : 0);// cout R[i] endl;}int sum 0;int tot 0;for (int i 0; i s.length(); i) {if (s[i] () {tot;sum (sum C(tot R[i] - 1, R[i] - 1) mod) % mod;}}cout sum;//Time_test();
}
