AtCoder Grand Contest 038

发表于 更新于 分类于

比赛链接：https://atcoder.jp/contests/agc038/tasks。

A - 01 Matrix

我无比智障的写了个贪心。。。

结果正解构造好简单啊啊啊

放的是我的贪心的代码，复杂度多个$\log$。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int a,b,n,m,c[maxn],id[maxn];
char s[maxn];

int cmp(int a,int b) {return c[a]>c[b];}

int main() {
    read(n),read(m),read(a),read(b);
    if(a*2>m||b*2>n) return puts("-1"),0;
    int px=-1,py;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            if(a*i+(m-a)*(n-i)==b*j+(n-b)*(m-j)) px=i,py=j;
    if(px==-1) return puts("-1"),0;
    // printf("%d %d\n",px,py);
    for(int i=1;i<=m;i++) if(i<=py) c[i]=b;else c[i]=n-b;
    for(int i=1;i<=n;i++) {
        int cnt;
        if(i<=px) cnt=a;
        else cnt=m-a;
        for(int j=1;j<=m;j++) id[j]=j;
        sort(id+1,id+m+1,cmp);
        for(int j=1;j<=m;j++) {
            int t=id[j];
            if(!c[t]) s[t]='0';
            else if(cnt) s[t]='1',cnt--,c[t]--;
            else s[t]='0';
        }puts(s+1);
    }
    return 0;
}

B - Sorting a Segment

我们枚举当前排序那一段，考虑排序完之后的数列出现过没。

首先特判不变的情况。

假设当前区间是$[i-k+1,i]$，那么上一个区间是$[i-k,i-1]$，这两种情况排序后相等当且仅当$[i-k,i]$最小值为$a_{i-k}$，最大值为$a_i$，手玩一下就可以发现。

并且没有其他的情况会导致相等，所以维护下最大值最小值就好了。

然后我无比智障的写了个线段树，因为单调队列难写

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,k,a[maxn];

#define mid ((l+r)>>1)
#define ls p<<1
#define rs p<<1|1

struct segment_tree {
    int mn[maxn<<2],mx[maxn<<2];

    void modify(int x,int v,int p=1,int l=1,int r=n) {
        if(l==r) return mn[p]=mx[p]=v,void();
        if(x<=mid) modify(x,v,ls,l,mid);
        else modify(x,v,rs,mid+1,r);
        mn[p]=min(mn[ls],mn[rs]);
        mx[p]=max(mx[ls],mx[rs]);
    }

    int query(int x,int y,int o,int p=1,int l=1,int r=n) {
        if(x<=l&&r<=y) return (o?mn:mx)[p];
        if(y<=mid) return query(x,y,o,ls,l,mid);
        else if(x>mid) return query(x,y,o,rs,mid+1,r);
        else if(!o) return max(query(x,y,o,ls,l,mid),query(x,y,o,rs,mid+1,r));
        else return min(query(x,y,o,ls,l,mid),query(x,y,o,rs,mid+1,r));
    }
}T;

int main() {
    read(n),read(k);for(int i=1;i<=n;i++) read(a[i]);
    int ans=0,bo=0,p=0;
    for(int i=1;i<=n;i++) {
        if(a[i]<a[i-1]) p=i;T.modify(i,a[i]);
        if(i<k) continue;
        if(i-k+1>=p) {bo=1;continue;}
        if(i==k) {ans++;continue;}
        if(T.query(i-k,i-1,1)==a[i-k]&&T.query(i-k+1,i,0)==a[i]) ;
        else ans++;
    }write(ans+bo);
    return 0;
}

C - LCMs

这种数论题都被做烂了。。。

设$b_i$表示$a_x=i$的个数，式子可以写成：

最后处理下重复的情况就行，那么莫比乌斯反演一下：

复杂度$O(n\log 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;
const int N = 1e6;

int n,a[maxn],s[maxn],ans,inv[maxn],pri[maxn],vis[maxn],mu[maxn],b[maxn],tot;

void gen() {
    inv[0]=inv[1]=1;
    for(int i=2;i<=N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    mu[1]=1;
    for(int i=2;i<=N;i++) {
        if(!vis[i]) pri[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*pri[j]<=N;j++) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}

int main() {
    gen();read(n);int sum=0;
    for(int i=1;i<=n;i++) read(a[i]),b[a[i]]++,sum=(sum+a[i])%mod;
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j+=i)
            s[i]=(s[i]+1ll*b[j]*j%mod)%mod;
    for(int d=1;d<=N;d++) {
        if(!s[d]) continue;
        int res=0;
        for(int t=1;t<=N/d;t++) res=(res+1ll*mu[t]*s[d*t]*s[d*t]%mod)%mod;
        res=1ll*res*inv[d]%mod;
        ans=(ans+res)%mod;
    }write((1ll*(ans-sum+mod)*inv[2]%mod+mod)%mod);
    return 0;
}

D - Unique Path

我想不出的神仙题。。

首先对于唯一路径的限制直接连边缩起来，连成一棵树。

对于不唯一的限制，如果两点在一个块中肯定不合法了。

假设我们当前有$c$个块，也就是说我们还需要连$m-n+c$条边。

考虑连通块之间怎么连边，如果我们对于一个连通块选出一个代表点，连边只在这些点之间进行，那么可以发现无论我们怎么连，块内的唯一路径的限制还是可以满足。

如果没有不唯一限制，那么只要满足$c-1\leqslant m-n+c\leqslant c(c-1)/2$就行了。

否则只要出现一个环就行，也就是$c\leqslant m-n+c\leqslant c(c-1)/2$。

注意到这种情况下如果只有两个以下个连通块是不合法的。

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
#include<bits/stdc++.h>
using namespace std;

#define int long long 

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int fa[maxn],n,m,t;
vector<pii > a;

int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

signed main() {
    read(n),read(m),read(t);int c=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=t;i++) {
        int x,y,z;read(x),read(y),read(z);
        if(z) a.pb(mp(x,y));
        else {
            x=find(x),y=find(y);
            if(x!=y) fa[x]=y,c++;
        }
    }c=n-c;
    for(auto x:a) if(find(x.fr)==find(x.sc)) return puts("No"),0;
    int l=a.size()?max(3ll,c):c-1,r=c*(c-1)/2;
    if(m-n+c>=l&&m-n+c<=r) puts("Yes");
    else puts("No");
    return 0;
}

E - Gachapon

神仙题啊啊啊啊啊，我对着官方题解看了好久才看懂的。。。

首先考虑$\min-\max$容斥，问题转化为了：对于所有集合$s$求有任意一个大于等于$b_i$就停止的期望步数乘上$(-1)^{|s|+1}$之和。

这个问题又可以转化为：求任意一个都没到$b_i$的情况数的期望出现次数，因为对于一种状态，假设它是第一个超出的状态，那么他前面一定都是不超出的状态，状态数就等于步数。

首先考虑确定了集合$s$的情况，假设当前状态是第$i$个出现了$x_i$，考虑出现这个状态的概率，根据一点组合数可以知道如果硬点选不到其他的数，概率就是：

如果考虑其他数可以发现出现概率是没有影响的，但是有影响的是当前状态出现了之后可能持续若干轮选其他的数，导致这个状态出现了多次。

更具体的，假设下一个选的数为当前集合里的数的概率为$P$，那么这个状态期望会持续$1/P$次，所以这个状态的贡献就是：

那么计算所有状态贡献和可以利用$dp$，设$f_{i,j}$表示当前状态$\sum a=i,\sum b=j$的贡献和，转移就枚举当前数出现了几次，最后在把前面的系数乘上去。

然后考虑怎么算对于每个集合的贡献和，其实这也非常简单了，考虑$dp$的时候加入一个数就多乘一个$-1$就行了。

复杂度为$O((\sum a)(\sum b)^2)$。

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
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 400+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int n,a[maxn],b[maxn],f[maxn][maxn],fac[maxn],ifac[maxn];

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}

void gen() {
    fac[0]=ifac[0]=1;
    for(int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[maxn-1]=qpow(fac[maxn-1],mod-2);
    for(int i=maxn-2;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}

int main() {
    gen();
    read(n);int s=0;
    for(int i=1;i<=n;i++) read(a[i]),read(b[i]),s+=a[i];
    f[0][0]=mod-1;
    int ss=0,tt=0;
    for(int i=1;i<=n;i++) {
        ss+=a[i],tt+=b[i];
        for(int j=ss;j>=a[i];j--) {
            for(int k=0;k<=tt;k++) {
                int w=1;
                for(int x=0;x<b[i]&&x<=k;x++) {
                    f[j][k]=(f[j][k]-1ll*f[j-a[i]][k-x]*w%mod*ifac[x]%mod+mod)%mod;
                    w=1ll*w*a[i]%mod;
                }
            }
        }
    }int ans=0;
    for(int i=1;i<=ss;i++) {
        int r=qpow(i,mod-2),w=1ll*r*ss%mod;
        for(int j=0;j<=tt;j++,w=1ll*w*r%mod)
            ans=(ans+1ll*f[i][j]*fac[j]%mod*w%mod)%mod;
    }
    write((ans+mod)%mod);
    return 0;
}