1093 Count PAT‘s (25 分)【难度: 一般 / 知识点: 前缀和 组合数】
知识点 25 组合 count 一般 PAT 前缀 难度
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805373582557184
PAT乙级的原题,这里不在赘述,就是前缀和,加简单的组合数。
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int N=1e5+10;
const int mod=1e9+7;
LL P[N],T[N];
int main(void)
{
string s; cin>>s;
s="0"+s;//加一个多余的字符让其下标从1开始
for(int i=1;i<s.size();i++) P[i]=P[i-1]+(s[i]=='P'?1:0);
for(int i=s.size()-1;i>=1;i--) T[i]=T[i+1]+(s[i]=='T'?1:0);
LL ans=0;
for(int i=1;i<s.size();i++)
if(s[i]=='A') ans=(ans+P[i-1]*T[i+1])%mod;
cout<<ans;
return 0;
}
相关文章
- 平面设计基础(PS)知识点总结
- java知识点总结(二)
- 云原生时代|分布式系统设计知识图谱(内含 22 个知识点)
- Java基础知识点整理(2021年最新版)
- Javascript + Dom知识点总结
- 归纳整理Python中的控制流语句的知识点
- java核心知识点学习----创建线程的第三种方式Callable和Future CompletionService
- 【BSP视频教程】BSP视频教程第25期:CAN/CANFD/CANopen专题,CAN知识点干货分享, 收发执行过程和错误帧处理(2023-01-03)
- Flutter 进阶篇-所有知识点架构
- Python之matplotlib:利用matplotlib绘制八象空间三维图案例(知识点包括散点图、折线图、标注文字、图例、三维坐标)之详细攻略
- Linux下安装Oracle的过程和涉及的知识点-系列6
- 【数据库通关之路】 MySQL 全路线学习知识点梳理(上)
- 鉴权必须了解的5个知识点:cookie,session,token,jwt,单点登录
- 2022C语言知识点大全【详细、必备】