Fake bullions[CF804F]

发表于 分类于

链接

CF

题解

一道二合一码农题。。。

不难发现如果我们算出一个点最多能有多少个人有金条，那么似乎可以组合数学去计算它。

然后此题就分为了两部分。

Part 1

第一部分是算出一个点最多或者最少有几个人有多少金条。

最少很容易求，下面只考虑最多的如何求。

考虑图中的一条边 $(u,v)$，可以发现，某个点的第 $j$ 个人能有金条当且仅当这两个点中存在一个人 $i$ 有金条且 $i\equiv j\pmod {\gcd(s_u,s_v)}$。

考虑图中的一条链，后面这个 $\gcd$ 就变为链中所有的 $s_u$ 的 $\gcd$ 了。

那么对于一个强连通分量，我们就可以在上面xjb走，因此上面的所有点中，上式的 $\gcd$ 就是强联通分量中所有的 $s_u$ 的 $\gcd$ 了。

考虑缩点，看看会变成什么样子。

由于原图中两个点中有且只有一条有向边，那么缩点之后还是会满足这个性质。但是又不能有环，因此这个缩点之后的图就可以看成一条链，链上一个点跟后面所有点都有连边的图。

然后你会发现不走链上的路径一定是不优的，因为走链的路径 $\gcd$ 不会变大。

那么最后就只剩下一条链了，拓扑排序依次计算即可。

这一部分时间复杂度为 $O(n^2+\sum s_i)$。

Part 2

这一部分相当于是给你两个长度为 $n$ 的数组 $l_i,r_i$。$n$ 个整数变量，第 $i$ 个变量取值在 $[l_i,r_i]$ 间。问在前 $A$ 大的数中选出 $B$ 个组成的下标集合的种类数。

枚举这些变量中，最小的且下标最大的一个下标 $i$。

贪心得考虑，为了让可以调剂的人数尽量多，这个人去 $r_i$ 的时候是最优的，这样就能有少一点人必须在 $B$ 中。

然后统计出来有多少个人必须比这个 $i$ 大的人数 $x$，有多少个人既可以比 $i$ 大，亦可以比 $i$ 小的人数 $y$。枚举 $y$ 中选了 $j$ 个人在 $B$ 集合中，那么方案数就是 $\binom{y}{j}\binom{x}{B-j-1}$。需要注意 $A$ 的限制就可以了。

这一部分时间复杂度为 $O(n^2)$。

$$ \$$

总的复杂度就是 $O(n^2+\sum s_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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=5005;
const int M=2e6+3;
int n;

namespace Part1{
    string s[N]; char t[N];
    int m[N];
    int st[N],dfn[N],low[N],top,cnt,belong[N],tim,in[N],g[N],now[N];
    bool instack[N],vi[M];
    vector<int> adj[N],vec[N],p[N];
    vector<bool> vis[N];
    inline void add(int x,int y)
    {
        adj[x].pb(y);
    }
    inline void dfs(int u,int pre)
    {
        instack[u]=1;
        st[++top]=u;
        dfn[u]=low[u]=++tim;
        for(auto v:adj[u])
            if(!dfn[v]) dfs(v,u),low[u]=min(low[u],low[v]);
            else if(instack[v]) low[u]=min(low[u],dfn[v]);
        if(low[u]==dfn[u])
        {
            cnt++;
            int d=0,v;
            do
            {
                v=st[top--];
                instack[v]=0;
                d=__gcd(d,m[v]);
                belong[v]=cnt;
                p[cnt].pb(v);
            }while(u!=v);
            g[cnt]=d;
        }
    }
    inline void work()
    {
        fo(i,1,n) if(!dfn[i]) dfs(i,0);
        fo(i,1,n)
            for(auto v:adj[i])
                if(belong[v]!=belong[i])
                    vec[belong[i]].pb(belong[v]);
        fo(i,1,cnt) sort(all(vec[i])),vec[i].resize(unique(all(vec[i]))-vec[i].begin());
        fo(u,1,cnt) for(auto v:vec[u]) in[v]++;
    }
    queue<int> q;
    inline void solve(int *mn,int *mx)
    {
        fo(i,1,n)
        {
            scanf("%s",t+1);
            fo(j,1,n) if(t[j]=='1') add(i,j);
        }
        fo(i,1,n)
        {
            m[i]=read();
            cin>>s[i];
            fo(j,0,m[i]-1) mn[i]+=(s[i][j]=='1');
        }
        work();
        fo(u,1,cnt) if(!in[u]) q.push(u);
        fo(u,1,cnt) now[u]=g[u],vis[u].resize(g[u]);
        for(int u;!q.empty();)
        {
            u=q.front(); q.pop();
            for(auto i:p[u])
            {
                fo(j,0,m[i]-1)
                    if(s[i][j]=='1')
                        vis[u][j%g[u]]=1;
            }
            for(auto v:vec[u])
            {
                --in[v];
                if(!in[v])
                {
                    q.push(v);
                    now[v]=__gcd(now[u],now[v]);
                    fo(i,0,g[u]-1)
                        if(vis[u][i])
                            vi[i%now[v]]=1;
                    fo(i,0,now[v]-1)
                        if(vi[i])
                            for(int j=i;j<g[v];j+=now[v])
                                vis[v][j]=1;
                    fo(i,0,now[v]-1) vi[i]=0;
                }
            }
        }

        fo(i,1,cnt)
        {
            int sum=0;
            fo(j,0,g[i]-1) if(vis[i][j]) sum++;
            for(auto v:p[i]) mx[v]=(1ll*m[v]*sum)/g[i];
        }
    }
}
const ll mod=1e9+7;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y){y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;return ans;}
namespace Part2{
    ll fac[N],inv[N];
    inline void init(int n)
    {
        fac[0]=1;
        fo(i,1,n) fac[i]=fac[i-1]*i%mod;
        inv[n]=Pow(fac[n],mod-2);
        fd(i,n,1) inv[i-1]=inv[i]*i%mod;
    }
    inline ll C(int n,int m)
    {
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    inline ll solve(int *l,int *r,int A,int B)
    {
        A=min(A,n);
        init(n);
        ll x,y,ans=0;
        fo(i,1,n)
        {
            x=y=0;
            fo(j,1,n)
            {
                if(l[j]>r[i]) x++;
                if(l[j]<=r[i]&&((r[i]<r[j])||(r[i]<=r[j]&&i>j))) y++;//???
            }
            if(x>=A) continue;
            int tmp=min(y,A-1-x);
            tmp=min(B-1,tmp);
            fo(j,0,tmp)
                if(B-j-1<=x)
                    ans=Add(ans,Mul(C(y,j),C(x,B-j-1)));
        }
        return ans;
    }
}
int A,B;
int mi[N],mx[N];
int main()
{
    //FO(na);
    n=read(); A=read(); B=read();
    Part1::solve(mi,mx);
    printf("%lld",Part2::solve(mi,mx,A,B));
    return 0;
}