A
B
这道题只需知道一个判断括号序列的性质，设左括号为 \(1\)，右括号为 \(-1\)，则对于 \([l,r]\) 满足其为合法括号序列就是 $\forall l \le i \le r,sum_i \ge suml-1 $，又因为每次只会 \(+1\) 或 \(-1\)，所以每次记录当前 \(sum\) 有多少的时候，就把 \(sum+1\) 的个数清零即可。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=1e9+7,inf=1e18,N=1e6+5;
int t=read(),n,sum[N],c[N],r[N],st[N],cnt[N],h[N];
char s[N];
signed main(){
while(t--){
scanf("%s",s+1);
n=strlen(s+1);
int mn=inf,mx=-inf;
for(int i=1;i<=n;i++){
c[i]=0;
if(s[i]=='(') sum[i]=sum[i-1]+1;
else sum[i]=sum[i-1]-1;
}
for(int i=0;i<=n;i++) mn=min(mn,sum[i]),mx=max(mx,sum[i]);
for(int i=0;i<=n;i++) sum[i]-=mn;
mx-=mn;
for(int i=0;i<=mx;i++) h[i]=0;
for(int i=n;i>=0;i--){
cnt[i]=++h[sum[i]];
h[sum[i]+1]=0;
}
for(int i=0;i<=mx;i++) h[i]=0;
int num=0,ans=0;
for(int i=0;i<=n;i++){
ans+=num*i%mod;
h[sum[i]+1]=0;
num=(num-h[sum[i]]*cnt[i]+mod)%mod;
h[sum[i]]++;
num=(num+h[sum[i]]*(cnt[i]-1))%mod;
}
cout<<ans<<'\n';
}
}
C
先写一个状压dp，接着就将转移放在矩阵上即可
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=1e9+7,inf=1e18;
int n=read(),st[6],num,vis[33];
struct matrix{
int ma[6][6];
inline void clear(){memset(ma,0,sizeof(ma));}
matrix friend operator*(matrix a,matrix b){
matrix c;
c.clear();
for(int i=0;i<6;i++) for(int j=0;j<6;j++) for(int k=0;k<6;k++){
c.ma[i][j]=(c.ma[i][j]+a.ma[i][k]*b.ma[k][j])%mod;
}
return c;
}
}tmp,ans;
inline int count(int x){
int cnt=0;
while(x) cnt+=(x&1),x>>=1;
return cnt;
}
signed main(){
for(int i=0;i<32;i++) if(count(i)==3&&(i&1)) st[num++]=i,vis[i]=num-1;
for(int i=0;i<num;i++){
int t=st[i]>>1;
for(int j=0;j<5;j++){
if((t>>j)&1) continue;
int op=t+(1<<j);
if(count(op)==3&&(op&1))
tmp.ma[i][vis[op]]++;
}
}
for(int i=0;i<6;i++) ans.ma[i][i]=1;
while(n){
if(n&1) ans=ans*tmp;
tmp=tmp*tmp,n>>=1;
}
cout<<ans.ma[0][0];
}
D
E
首先观察题目，可以发现若所有人同时增加或减少自己传的球的个数，最后的结果不会改变，设 \(x_i\) 为这个人传的球的个数，我们只需算出 \(\min_{i=1} ^{n} x_i = 0\) 的传球序列的贡献即可，可还是有些麻烦，考虑容斥，求出所有 \(x_i \in [0,a_i]\) 的贡献再减去 \(x_i \in [1,a_i]\) 的贡献即可。
接着就是推式子，先将式子列出来：
\[f_n = \prod_{i=1}^{n} a_i-x_i+x_{i-1} \]拆一下就可以得到：
$f_n = a_n\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) - x_n\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) + x_{n-1}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) $
\(f_n = (a_n-x_n)\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) + x_{n-1}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1})\)
\(f_n = (a_n-x_n)f_{n-1} + x_{n-1}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1})\)
可是后面的一部分连着 \(x_{n-1}\) 所以并不能在时限内处理，所以我们单独解决。
\[g_n = x_{n}\prod_{i=1}^{n}(a_i-x_i+x_{i-1}) \]同样的道理，直接暴力拆开:
\(g_n = x_{n}a_{n}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) - x_{n}^{2}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1}) + x_{n}x_{n-1}\prod_{i=1}^{n-1}(a_i-x_i+x_{i-1})\)
\(g_n = (x_n a_n - x_n^{2})f_{n-1} + x_ng_{n-1}\)
接着我们就可以把 \(x_n\) 给替换掉(假设当前求的是 \(x_i \in [0,a_i]\) 的贡献):
设:
\(S(x)=\frac{x \times (x+1)}{2}\)
\(S2(x)=\frac{x \times (x+1) \times (2x+1)}{6}\)
\(f_n = S(a_n) f_{n-1} + (a_n + 1)g_{n-1}\)
\(g_n = (S(a_n) a_n - S2(a_n))f_{n-1} + S(a_n)g_{n-1}\)
注意这个转移其实是个环，而 \(g_n\) 表示的是之前上一个人传过来球的方案，所以只需要在第一个人上判一下是 \(f_1 = 1\) 还是 \(g_1 =1\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=998244353,inf=1e18,N=1e5+5,inv2=499122177,inv6=166374059;
int n,a[N],dp[N][2];
inline int S(int x){return x*(x+1)%mod*inv2%mod;}
inline int S2(int x){return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
inline int calc(int x,int y){
memset(dp,0,sizeof(dp));
dp[1][x]=1;
for(int i=2;i<=n+1;i++){
dp[i][0]=(S(a[i]-y)*dp[i-1][0]%mod+(a[i]+1-y)*dp[i-1][1]%mod)%mod;
dp[i][1]=((S(a[i])*a[i]%mod-S2(a[i])+mod)*dp[i-1][0]%mod+S(a[i])*dp[i-1][1])%mod;
}
return dp[n+1][x];
}
signed main(){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
a[n+1]=a[1];
cout<<(((calc(1,0)+calc(0,0))-(calc(0,1)+calc(1,1)))%mod+mod)%mod<<'\n';
}
F
首先我们可以写出一个 naive 的dp式子，设 \(dp_{i,j}\) 表示第 \(i\) 个点，当前经过了 \(j\) 个障碍当前的路径数，可以列出式子：
\[dp_{i,j} = \sum_{\forall k , x_k \le x_i \wedge y_k \le y_i} dp_{k,j-1} \times calc(k,i) \]对于 \(calc(k,i)\) 就等于 $\binom{x_i-x_k+y_i-y_k}{x_i-x_k} $。
显然这个式子是有问题的，因为这两个点之间有可能还会经过其他障碍。但我们可以扩大这个dp的限制，令 \(f_{i,j}\) 表示第 \(i\) 个点，当前至少经过了 \(j\) 个点。
这时候你就发现可以容斥了，因为 \(f_{i,j} = \sum_{i=1}^{j} dp_{i,j}\)，然后就解决了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=1e9+7,inf=1e18,N=2e3+5,M=2e5+5;
int n,m,k,S,f[N][25],dp[N][25],jie[M],invj[M],inv[M],res[25],ans[25];
struct node{int x,y;}p[N];
inline bool cmp(node a,node b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
inline void init(){
jie[0]=jie[1]=invj[0]=invj[1]=inv[1]=1;
for(int i=2;i<=M-5;i++)
jie[i]=jie[i-1]*i%mod,
inv[i]=(mod-mod/i)*inv[mod%i]%mod,
invj[i]=invj[i-1]*inv[i]%mod;
}
inline int C(int x,int y){
if(x<y) return 0;
return jie[x]*invj[y]%mod*invj[x-y]%mod;
}
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
signed main(){
n=read(),m=read(),k=read(),S=read();
for(int i=1;i<=k;i++) p[i].x=read(),p[i].y=read();
init();
sort(p+1,p+k+1,cmp);
p[0].x=1,p[0].y=1;
dp[0][0]=1;
for(int i=1;i<=k;i++){
for(int j=0;j<i;j++){
if(p[j].x<=p[i].x&&p[j].y<=p[i].y)
for(int o=1;o<=22;o++){
(f[i][o]+=dp[j][o-1]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%mod)%=mod;
if(o==22) (f[i][o]+=dp[j][o]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%mod)%=mod;
}
}
for(int o=1;o<=22;o++) dp[i][o]=(f[i][o]-f[i][o+1]+mod)%mod;
}
for(int i=0;i<=k;i++){
for(int o=0;o<=22;o++)
(res[o]+=dp[i][o]*C(n-p[i].x+m-p[i].y,n-p[i].x)%mod)%=mod;
}
int as=0;
for(int o=0;o<=22;o++) ans[o]=(res[o]-res[o+1]+mod)%mod;
for(int o=0,now=S;o<=22;o++,now=(now+1)/2) as=(as+now*ans[o]%mod)%mod;
cout<<as*qpow(C(n+m-2,n-1),mod-2)%mod<<'\n';
}
/*
3 3 3 11
1 1
2 1
2 3
*/
G
又是一道推式子的题，首先简单推一下，可以得到这个图长这样：
接着你发现深度是编号的二进制数中 \(1\) 的个数，所以可以得到这个递推式子：
\[f_n = 2f_{n-1} + \binom{2i-2}{d-1} \]再改一下：
\[f_n = \sum_{i=1}^{n} 2^{n-i} \times \binom{2i-2}{d-1} \]为了方便，\(n=n-1 , d=d-1\)
则可得到：
\[f_n = \sum_{i=0}^{n} 2^{n-i} \times \binom{2i}{d} \]接着由于 \(n\) 过大，而且组合数中含有固定的 \(d\) 这一项，所以我们考虑将组合数拆开，来引出新的递推式子:
$dp_d $
\(=\sum_{i=0}^{n} 2^{n-i} \times \binom{2i}{d}\)
\(= \sum_{i=0}^{n} 2^{n-i} \times (\binom{2i-2}{d-2}+2\binom{2i-2}{d-1}+\binom{2i-2}{d})\)
\(= \sum_{i=0}^{n}\binom{2i-2}{d-2} 2^{n-i} + 2\sum_{i=0}^{n}\binom{2i-2}{d-1} 2^{n-i} + \sum_{i=0}^{n}\binom{2i-2}{d} 2^{n-i}\)
\(= \frac{1}{2}\sum_{i=0}^{n-1}\binom{2i}{d-2} 2^{n-i} + \sum_{i=0}^{n-1}\binom{2i}{d-1} 2^{n-i} + \frac{1}{2} \sum_{i=0}^{n-1}\binom{2i}{d}2^{n-i}\)
\(= \frac{1}{2}(dp_{d-2} - \binom{2n}{d-2}) + (dp_{d-1} - \binom{2n}{d-1}) + \frac{1}{2} (dp_d - \binom{2n}{d})\)
\(= dp_{d-2} + 2dp_{d-1} - \binom{2n}{d-2} - 2\binom{2n}{d-1} - \binom{2n}{d}\)
最后复杂度: \(O(d)\)。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int inf=1e18,N=1e7+5;
int n,d,mod,f[N],num[N],inv[N];
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
signed main(){
n=read()-1,d=read()-1,mod=read();
inv[1]=1,f[0]=qpow(2,n+1)-1,num[0]=1;
for(int i=2;i<=d;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=d;i++) num[i]=num[i-1]*(2*n-i+1)%mod*inv[i]%mod;
f[1]=2*f[0]-2*num[0]-num[1];
for(int i=2;i<=d;i++){
f[i]=2*f[i-1]+f[i-2]-2*num[i-1]-num[i-2]-num[i];
f[i]=(f[i]%mod+mod)%mod;
}
cout<<f[d]<<'\n';
}
H
其实这道题只是一道套路题。
首先先令 \(c\) 表示第 \(k\) 小的分数，你再设出这么一个dp: \(dp_{i,j}\) 表示目前第 \(i\) 个人，前面有 \(j\) 个人已经被选入决赛。
但这个dp还要再改一下，因为你要保证 \(c\) 被选了进去，又因为被选入的人中分数为 \(c\) 的人得到编号必然是一个前缀，所以就再加一维 \(0/1\) 表示最后一个被选入的 \(c\) 是否已经被加入。
接着正着做一遍dp再倒着做一遍dp，得到数组 \(f\) 和 数组 \(g\)。
再枚举一下每个人，被选入决赛的方案数，一共分三种情况:
- 最后一个 \(c\) 恰好是这个人
- 最后一个 \(c\) 在这个人之前
- 最后一个 \(c\) 在这个人之后
然后就做完了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=998244353,N=2e2+5;
int n,k,l[N],r[N];
double f[N][N][2],g[N][N][2],ans[N][2];
inline void init(int c){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[0][0][0]=g[n+1][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
int num=r[i]-l[i]+1;
if(j) f[i][j][0]+=f[i-1][j-1][0]*max(0,min(num,r[i]-c+1));
f[i][j][0]+=f[i-1][j][0]*max(0,min(num,c-l[i]));
if(j) f[i][j][1]+=f[i-1][j-1][1]*max(0,min(num,r[i]-c));
f[i][j][1]+=f[i-1][j][1]*max(0,min(num,c-l[i]+1));
if(l[i]<=c&&c<=r[i]&&j) f[i][j][1]+=f[i-1][j-1][0];
f[i][j][0]/=(double)(r[i]-l[i]+1),f[i][j][1]/=(double)(r[i]-l[i]+1);
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<k;j++){
int num=r[i]-l[i]+1;
if(j) g[i][j][1]+=g[i+1][j-1][1]*max(0,min(num,r[i]-c+1));
g[i][j][1]+=g[i+1][j][1]*max(0,min(num,c-l[i]));
if(j) g[i][j][0]+=g[i+1][j-1][0]*max(0,min(r[i]-c,num));
g[i][j][0]+=g[i+1][j][0]*max(0,min(c-l[i]+1,num));
if(l[i]<=c&&c<=r[i]&&j) g[i][j][1]+=g[i+1][j-1][0];
g[i][j][0]/=(double)(r[i]-l[i]+1),g[i][j][1]/=(double)(r[i]-l[i]+1);
}
}
}
signed main(){
int mn=1e9,mx=0;
n=read(),k=read();
for(int i=1;i<=n;i++) l[i]=read(),mn=min(mn,l[i]);
for(int i=1;i<=n;i++) r[i]=read(),mx=max(mx,r[i]);
for(int c=mn;c<=mx;c++){
init(c);
for(int i=1;i<=n;i++){
for(int front=0;front<k;front++){
int num=(front+1)%4/2,op=r[i]-l[i]+1;
if(l[i]<=c&&c<=r[i]) ans[i][num]+=f[i-1][front][0]*g[i+1][k-front-1][0];
ans[i][num]+=f[i-1][front][1]*g[i+1][k-front-1][0]*max(0,min(op,r[i]-c));
ans[i][num]+=f[i-1][front][0]*g[i+1][k-front-1][1]*max(0,min(op,r[i]-c+1));
}
}
}
for(int i=1;i<=n;i++){
ans[i][0]/=(double)(r[i]-l[i]+1),ans[i][1]/=(double)(r[i]-l[i]+1);
printf("%.10lf %.10lf\n",ans[i][0],ans[i][1]);
}
}
/*
3 2
1 1 2
2 3 3
*/
I
很妙的题
首先先将这些序列离散化：1324，1243，1432 。
\(ans= calc(1324)-calc(1243)-calc(1432)\)
\(ans= ( calc(1X2X)-calc(1423) ) - ( calc(12XX) - calc(1234) ) -( calc(14XX) - calc(1423) )\)
\(ans=calc(1X2X) - calc(12XX) + calc(1234) - calc(14XX)\)
\(ans=calc(1X2X) - calc(12XX) + calc(1234) - (calc(1XXX)-calc(12XX)-calc(13XX))\)
\(ans=calc(1X2X) + calc(1234) + calc(13XX) - calc(1XXX)\)
接着对每一个计算即可。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define pir pair<int,int>
#define mkp(a,b) make_pair(a,b)
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=16777216,inf=1e18,N=2e5+5;
int n,p[N],l[N],r[N],ans;
struct tree{
int t[N];
inline void clear(){memset(t,0,sizeof(t));}
inline void add(int p,int k){for(;p<=n;p+=lowbit(p)) t[p]+=k;}
inline int ask(int p){int res=0; for(;p;p-=lowbit(p)) res+=t[p]; return res;}
}tre;
signed main(){
n=read();
for(int i=1;i<=n;i++) p[i]=read();
for(int i=1;i<=n;i++) l[i]=tre.ask(p[i]),r[i]=p[i]-l[i]-1,tre.add(p[i],1);
for(int i=1;i<=n;i++) ans=ans-(n-i-r[i])*(n-i-r[i]-1)*(n-i-r[i]-2)/6;
tre.clear();
ans%=mod;
for(int i=1;i<=n;i++) ans=ans+tre.ask(p[i])*(n-i-r[i]),tre.add(p[i],l[i]);
tre.clear();
ans%=mod;
for(int i=1;i<=n;i++) ans=ans+(l[i]*(i-1)-l[i]*(l[i]-1)/2-tre.ask(p[i]))*(n-i-r[i]),tre.add(p[i],i);
tre.clear();
ans%=mod;
for(int i=n;i>=1;i--) ans=ans+(tre.ask(p[i])-r[i]*(r[i]+1)/2)*(n-r[i]-i),tre.add(p[i],p[i]);
ans%=mod;
cout<<(ans+mod)%mod<<'\n';
}