2017 CCPC秦皇岛 B

枚举一对匹配的括号，里面和外面都是catalan数。注意到相同距离的括号对可以合并，枚举距离计一下数即可。过程中要预处理阶乘和逆元。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000005;
ll n, mod, b[maxn], a[maxn], A, B;
ll inv[maxn];
ll fac[maxn];
void init(){
inv[0]=inv[1]=1;
fac[0]=fac[1]=1;
for(int i=2;i<=2*n;i++){
inv[i]=inv[mod%i]*(mod-mod/i)%mod;
fac[i]=fac[i-1]*i%mod;
}
for(int i=1;i<=2*n;i++){
inv[i]=inv[i-1]*inv[i]%mod;
}
}
ll catalan(ll n){
if(n==0)return 1;
ll ret=fac[2*n];
ret=ret*inv[n+1]%mod;
ret=ret*inv[n]%mod;
return ret;
}
ll power(ll n, ll p){
ll ans=1;
ll base=n;
while(p){
if(p&1)ans=ans*base%mod;
base=base*base%mod;
p>>=1;
}
return ans;
}
ll Inv(ll num){
return power(num, mod-2);
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%lld%lld%lld%lld%lld", &n, &mod, &b[0], &A, &B);
for(ll i=1;i<=2*n;i++){
b[i]=(A*b[i-1]+B)%mod;
a[i]=a[i-1]+b[i]+1;
}
for(ll i=1;i<=2*n;i++){
a[i]=(a[i]+a[i-1])%mod;
}
init();
ll p=0;
for(ll i=1;i<=n;i++){
ll tmp=(a[n*2]-a[i*2-1]-a[n*2-i*2+1]+2*mod)%mod;
tmp=tmp*catalan(i-1)%mod;
tmp=tmp*catalan(n-i)%mod;
p=(p+tmp)%mod;
}
ll q=catalan(n);
ll ans=p*Inv(q)%mod;
printf("%lldn", ans);
}
}

最后

以上就是沉默歌曲为你收集整理的2017 CCPC秦皇岛 B的全部内容，希望文章能够帮你解决2017 CCPC秦皇岛 B所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。