比赛链接：https://codeforces.com/contest/1924/problem/D

A

弱智题，每次选最远就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=26;
int nex[N][M],las[M];
char st[N],ans[N];
int n,k,m;
bool work(){
    scanf("%d%d%d",&n,&k,&m);
    scanf("%s",st+1);
    for(int i=0;i<k;i++)las[i]=m+1;
    for(int i=m;i>=1;i--){
        for(int j=0;j<k;j++)nex[i][j]=las[j];
        las[st[i]-'a']=i;
    }
    for(int j=0;j<k;j++)nex[0][j]=las[j];
    int now=0;
    for(int i=1;i<=n;i++){
        int maxpos=0,num=0;
        for(int j=0;j<k;j++){
            if(nex[now][j]>maxpos)maxpos=nex[now][j],num=j;
        }
        ans[i]=num+'a';
        now=maxpos;
        if(now>m){
            for(int j=i+1;j<=n;j++)ans[j]='a';
            ans[n+1]='\0';
            return 0;
        }
    }
    return 1;
}
int main(){
    int T;
    scanf("%d",&T);
    // T=1;
    while(T--){
        if(work()){
            printf("Yes\n");
        }
        else{
            printf("No\n%s\n",ans+1);
        }
    }
    return 0;
}

B

典中典线段树题，我还以为有高论，想多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+5;
const int NN=6e5+5;
struct Segment{
    int lc,rc;
    LL lazy,c1,c2,d1,d2;
}tr[NN];int len;
void updata(int x){
    tr[x].c1=tr[tr[x].lc].c1+tr[tr[x].rc].c1;
    tr[x].c2=tr[tr[x].lc].c2+tr[tr[x].rc].c2;
}
void pushlazy(int x,LL c){
    tr[x].c1+=c*tr[x].d1;
    tr[x].c2+=c*tr[x].d2;
    tr[x].lazy+=c;
}
void pushdown(int x){
    if(tr[x].lazy){
        pushlazy(tr[x].lc,tr[x].lazy);
        pushlazy(tr[x].rc,tr[x].lazy);
        tr[x].lazy=0;
    }
}
int bt(int l,int r){
    int x=++len;
    tr[x].d1=r-l+1;tr[x].d2=1ll*(r+l)*(r-l+1)/2;
    if(l<r){
        int mid=(l+r)>>1;
        tr[x].lc=bt(l,mid);
        tr[x].rc=bt(mid+1,r);
    }
    return x;
}
void change(int x,int l,int r,int ll,int rr,LL c){
    if(ll>rr || r<ll || l>rr)return ;
    if(l>=ll && r<=rr){
        pushlazy(x,c);
        return ;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    change(tr[x].lc,l,mid,ll,rr,c);
    change(tr[x].rc,mid+1,r,ll,rr,c);
    updata(x);
}
LL findans(int x,int l,int r,int id){
    if(l>id)return 0ll;
    if(r<=id)return (id+1)*tr[x].c1-tr[x].c2;
    pushdown(x);
    int mid=(l+r)>>1;
    return findans(tr[x].lc,l,mid,id)+findans(tr[x].rc,mid+1,r,id);
}
int n,m,q;
set<int> pos;
LL V[N];bool v[N];int p[N];
int ll[N];//(ll[i],i)
void modif(int l,int r,LL c){
    if(l>r)return ;
    change(1,1,n,l,r,c);
    change(1,1,n,r+1,r+1,-c*(r-l+1));
}
void print(){
    for(int i=1;i<=n;i++){
        printf("%lld ",findans(1,1,n,i)-findans(1,1,n,i-1));
    }
    printf("\n");
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);x=n-x+1;
        v[x]=1;
        p[i]=x;
        pos.insert(x);
    }
    for(int i=1;i<=m;i++){
        LL x;scanf("%lld",&x);
        V[p[i]]=x;
    }
    bt(1,n);
    int pre=1;
    for(int i=2;i<=n;i++){
        if(!v[i])continue;
        ll[i]=pre;pre=i;
        modif(ll[i]+1,i-1,V[i]);
    }
    // print();
    for(int i=1;i<=q;i++){
        int t;scanf("%d",&t);
        if(t==1){
            int x,val;scanf("%d%d",&x,&val);x=n-x+1;
            v[x]=1;V[x]=val;pos.insert(x);
            int nex=*pos.upper_bound(x);
            modif(ll[nex]+1,nex-1,-V[nex]);
            ll[x]=ll[nex];
            modif(ll[x]+1,x-1,V[x]);
            ll[nex]=x;
            modif(ll[nex]+1,nex-1,V[nex]);
            // print();
        }
        else{
            int l,r;scanf("%d%d",&l,&r);l=n-l+1;r=n-r+1;
            swap(l,r);
            printf("%lld\n",findans(1,1,n,r)-findans(1,1,n,l-1));
        }
    }
    return 0;
}

C

一个显然的事情，你考虑在折过一次的的纸上，去考虑接下来折纸产生的折痕，在这一次折纸展开后会变成什么样，可以发现：

赛时唐了，以为要写矩阵，但实际上不用，直接推式子就行了。

最终 $\frac{M}{V}=1-\frac{2}{\sqrt{2}^{n+1}+\sqrt{2}^{n}-\sqrt{2}}$ ，直接算就行了。

题解说奇怪的模数是为了保证分母不为 $0$ ，说是不能让 $2$ 能够开根，我推测用上面的式子精细的讨论一下 $n$ 的奇偶，可能也能分析出来，但我懒得想了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=999999893,ni2=(mod+1)/2;
struct node{
    LL x,y;//x+y*sqrt(2)
};
node operator*(node x,node y){
    return {(x.x*y.x+x.y*y.y*2)%mod,(x.x*y.y+x.y*y.x)%mod};
}
node operator*(node x,LL y){
    return {(x.x*y)%mod,(x.y*y)%mod};
}
node operator+(node x,node y){
    return {(x.x+y.x)%mod,(x.y+y.y)%mod};
}
node operator-(node x,node y){
    return {(x.x-y.x+mod)%mod,(x.y-y.y+mod)%mod};
}
node ksm(node x,LL y){
    node ans={1ll,0};
    while(y){
        if(y&1)ans=ans*x;
        x=x*x;y>>=1;
    }
    return ans;
}
LL ksm(LL x,LL y){
    LL ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        x=x*x%mod;y>>=1;
    }
    return ans;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        node x={0ll,1};
        node y=ksm(x,n+1)-node{0ll,1}+ksm(x,n);
        node z=node{y.x,mod-y.y}*ksm( (y.x*y.x-y.y*y.y*2%mod+mod)%mod ,mod-2);
        node ans=node{1ll,0ll}-z*2;
        printf("%lld\n",ans.y);
    }
    return 0;
}

D

唐了。

这道题目我一开始的思路是，一个显然的事情，最终序列一定是一堆合法括号序列，然后用 $)))((($ 插入到两个合法括号序列中间，然后就有了我最开始的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int N=1e4+5;
const int L=10000;
LL fc[N],nfc[N];
void init(){
    fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=L;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
    for(int i=2;i<=L;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
}
LL C(int x,int y){
    if(x<y || y<0)return 0ll;
    return fc[x]*nfc[y]%mod*nfc[x-y]%mod;
}
LL goal_fu(int x,int len){
    x--;len--;
    if(x<0)x=-x;
    if(x>len)return 0;
    assert((len&1)==(x&1));
    return C(len,(len-x)>>1);
}
LL goal(int x,int len){
    return (goal_fu(x,len)-goal_fu(-x,len)+mod)%mod;
}
int main(){
    init();
    int T;scanf("%d",&T);
    while(T--){
        int n,m,k;scanf("%d%d%d",&n,&m,&k);
        if(n<k || m<k){
            printf("0\n");
            continue;
        }
        n-=k;m-=k;
        LL ans=0;
        for(int i=1;i<=k;i++){
            LL now=goal(i,k+k-i);
            ans=(ans+now*C(n+m+i,i))%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

但实际上可以直接用折线法得到最终答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int N=1e4+5;
const int L=10000;
LL fc[N],nfc[N];
void init(){
    fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=L;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
    for(int i=2;i<=L;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
}
LL C(int x,int y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
int main(){
    init();
    int T;scanf("%d",&T);
    while(T--){
        int n,m,k;scanf("%d%d%d",&n,&m,&k);
        if(n<k || m<k){
            printf("0\n");
            continue;
        }
        printf("%lld\n",(C(n+m,k)-C(n+m,k-1)+mod)%mod);
    }
    return 0;
}

显然两种做法后面一种更加优秀，而且也不算难。

但是赛时就是没想出来，警钟敲烂。

已将上面两种做法的最关键部分全部写入组合计数练习，引以为戒，警钟敲烂。

E

做法已加入《组合计数练习》。

简单来说就是用排列考虑就行了。

时间复杂度：$O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int N=2e6+5;
LL nfc[N];
void init(){
    const int L=2e6+1;
    nfc[0]=nfc[1]=1;for(int i=2;i<=L;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
}
int main(){
    init();
    int T;scanf("%d",&T);
    while(T--){
        LL n,m,k;scanf("%lld%lld%lld",&n,&m,&k);k--;
        if(n*m<=k){
            printf("0\n");
            continue;
        }
        LL ans=1;
        {
            LL l=k/n+1;
            for(int i=l;i<m;i++)ans=(ans+nfc[n-1+i])%mod;
        }
        {
            LL l=k/m+1;
            for(int i=l;i<n;i++)ans=(ans+nfc[i+m-1])%mod;
        }
        {
            for(int i=1;i<n;i++){
                LL l=k/i+1,r=m-1;
                if(l<=r)ans=(ans+2*(nfc[i+l-1]-nfc[i+r]+mod))%mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题外话

在想这道题目的时候发现了一个具有意思的组合意义，可惜没法扩展。

考虑一个弱化版的问题：

令 $m=1$ ，问出现 $k*1$ 的纸张的概率。

这么考虑这个问题：

现在从 $n-1$ 开始考虑，考虑到 $x$ 时，有 $\frac{1}{x}$ 的概率选中他，不难发现这与原过程等价。

这样，问题转化为选中 $k$ 的概率，显然就是 $\frac{1}{k}$ 了。

F

咕咕咕。