[关闭]
@ArrowLLL 2017-04-06T10:55:07.000000Z 字数 1645 阅读 973

组合数学例题:Codeforces#round404 - D(785D)

组合数学 算法


主页地址 :月光森林


仍然任性地践行不写题解的原则,于是默默地把标题改成了组合数学例题。但是实际上还是一篇题解,大家就默默地看不要吐槽就好。

OK, link start:

题目描述

先给出原题链接 : codeforces#Round404(div-2)-D

一个RSBS(标准简式括号表达式)是指一个只包含'(' 和 ')' 的长度为n的字符串,且满足一下条件:

现在给定一个长度为 的括号表达式 s ,问 s 中有多少个子串是 RSBS。

所谓子串是指删掉 s 中的一些字符得到的串。所以题目实际上是在问有多少种删除字符的方式可以获得一个RSBS, 或者说是从原串 s 中选择出一定字符可以组成一个RSBS的不同方法。

解题思路

假如 s 串中一共有 m 个左括号,则可以将从 s 中得到的RSBS作 m 个划分, 每个划分是以第 i ()个左括号为中心得到的RSBS。

因此,可以以左括号("(")的位置作为枚举对象。

假设对于某个位置处的左括号,它左边有 个左括号,右边有 个右括号, 则对于这个确定的左括号来说, 以它为中心的得到的RSBS的数量满足:

对于这个公式,实际上可以化简 ,直接上结论:

这相当于连续摆放的 个物品,从中选取 个物品。

这个题目的难点就在于化简,比赛当时想到了这个思路和公式,但就是想不出来怎么化简。比赛结束看讨论才知道的:

化简

而如何计算组合数,可以从本人之前的博客查看,根据数据范围,这个地方使用的是公式法+逆元。

代码

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const LL maxn(2e5 + 5);
  5. char bct[maxn];
  6. int r[maxn], n; // r[]数组记录右括号的数量
  7. /******** 计算C(n, m) 的算法********/
  8. const LL mod(1e9 + 7);
  9. LL jC[maxn];
  10. LL niY(LL t)
  11. {
  12. LL p = mod - 2, res = 1;
  13. while(p)
  14. {
  15. if(p & 1) res = res * t % mod;
  16. t = t * t % mod;
  17. p >>= 1;
  18. }
  19. return res;
  20. }
  21. void init()
  22. {
  23. jC[0] = jC[1] = 1;
  24. for(int i = 2; i < maxn; i++)
  25. jC[i] = jC[i - 1] * i % mod;
  26. }
  27. LL calC(LL n, LL m)
  28. {
  29. LL ma = niY(jC[m]) * niY(jC[n - m]) % mod;
  30. return (jC[n] * ma % mod) % mod;
  31. }
  32. /******** 计算C(n, m) 的算法********/
  33. int main()
  34. {
  35. init();
  36. //freopen("data.in", "r", stdin);
  37. while(~scanf("%s", bct))
  38. {
  39. n = strlen(bct);
  40. r[n] = 0;
  41. for(int i = n - 1; i >= 0; i--)
  42. r[i] = bct[i] == ')' ? r[i + 1] + 1 : r[i + 1];
  43. LL ans = 0;
  44. for(int i = 0, j = 0; i < n; i++)
  45. if(bct[i] == '(')
  46. {
  47. ans = ans + calC(j + r[i], r[i] - 1);
  48. ans %= mod, j ++;
  49. }
  50. printf("%I64d\n", ans);
  51. }
  52. return 0;
  53. }

以上です~

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注