@codeforces - 804F@ Fake bullions

不念不忘少年蓝@ 2023-06-01 13:57 15阅读 0赞

*  @description@
 *  @solution@
    
     *  @part - 1@
     *  @part - 2@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

有 n 个 gangs，第 i 个 gangs 有 si 个人，编号为 0...si - 1。在所有的人中，有些人曾经通过特殊途径拿到了**一根**真正的 gold。

现在距离他们拿到 gold 已经过去 \\(10^\{100\}\\)（假装他们都不会死）。在这些年中，他们进行了若干次 gold 的交易，方法如下：  
这 n 个 gangs 形成了一张竞赛图。在第 i 年，第 u 个 gang 的第 i mod su 个人会向第 v 个 gang 的第 i mod sv 个人发送一根虚假的 gold。  
当然是有前提的，前提是 u 有连向 v 的边，且发送者有根 gold（不管是真是假）且接受者没有 gold（不管是真是假）。

现在，这些 gangs 开始贩卖 gold。真实的 gold 显然是可以直接卖出去的，虚假的 gold 可能卖得出去也可能卖不出去。然后，这些 gangs 按照自己贩卖出去的 gold 数量排序（相同的随便排）。  
现询问在所有情况（虚假的 gold 卖出去或卖不出去 / gold 数量相同内部排序）下，我从 gold 数量前 a 多的 gangs 中选择大小为 b 的集合，最终可以选出多少可能的集合。

**Input**  
第一行包含三个整数 n, a, b (1 ≤ b ≤ a ≤ n ≤ 5·10^3)，含义如上。  
接下来 n 行，每行包含一个长度为 n 的 01 串。若第 i 行第 j 列为 1 则有一条 i 到 j 的边。  
接下来 n 行，每行一开始一个 si (1 ≤ si ≤ 2·10^6) 含义如上，接着是长度为 si 的 01 串，其中第 j 个数为 1 则第 i 个 gang 的第 j 个人有一根真实的 gold（注：题面在此处有误。原题面所说的第 j 个数为 0 表示有 gold，但其实是 1）。  
保证 si 之和 ≤ 2·10^6。

**Output**  
输出一个单独整数表示答案 mod 10^9 + 7。

**Examples**  
**Input**  
2 2 1  
01  
00  
5 11000  
6 100000  
**Output**  
2  
**Input**  
5 2 1  
00000  
10000  
11011  
11000  
11010  
2 00  
1 1  
6 100110  
1 0  
1 0  
**Output**  
5

## @solution@ ##

gang,gold,真实......难道......是黄金体验镇魂曲\[GoldExperienceRequiem\]！乔鲁诺，这也在你的计划之中吗！

题意绕晕人系列。  
为什么这么绕呢？因为这个题。。。其实是两个题拼起来的。。。

### @part - 1@ ###

先考虑求出每个 gang 的真实 gold 的数量与总 gold 的数量。  
前一个很好求，根据它的输入就可以直接算，主要是看后面一个。

假如第 u 个 gang 的 x 能够在某一时刻向第 v 个 gang 的 y 发送 gold，即存在一个 i 使得 i mod su = x 且 i mod sv = y，则根据扩展欧几里得可以得到 x = y mod gcd(su, sv)。  
将上面那个结论推广一下，假如 u 通过某一路径到达 v，则 u 中的 x 能够向 v 中的 y 发送金条，仅当 x = y mod (路径上所有点的 gcd)。  
所以：从 u 到 v 肯定绕远路更优（模数即 gcd 更小）。

根据竞赛图的性质，我们将原图强连通缩点，则强连通内必然存在一条哈密顿回路。  
我们从 u 到 v 的最远路径一定是将 u, v 之间所有的强连通分量都走完，而哈密顿回路保证了这样一条路径的存在。  
所以，我们可以考虑把一个强连通缩成一个新的 gang'，这个 gang' 的人数等于强连通内部的所有点的人数的 gcd，而这个 gang' 的金条可以通过强连通内部的点已经拥有的真 gold 得到。

因为尽量绕远路，所以缩完点后一定是按照拓扑序从前往后，相邻的 gang' 之间才转移。

怎么通过一个强连通的信息反推出一个点的信息呢？假如这个点的大小为 s1，强连通的大小为 s2，强连通的 gold 数量为 g，则这个点的 gold 数量 = s1/s2\*g。  
因为 s2 是所有 s1 的 gcd，所以一定能够得到一个整数。

### @part - 2@ ###

现在考虑已知每个 gang 的真实 gold 的数量与总 gold 的数量（其实也就是能卖出去的最小 gold 数 mn 与最大 gold 数 mx），怎么求题目要求我们求的东西。  
考虑最暴力的：枚举一个大小为 B 的集合，判定这个集合是否能够同时进前 A 大，显然如果要求这个集合内所有点取 mx，而集合外的所有点取 mn 才最有可能合法。  
考虑这个集合中最小的那个（为了避免重复计数，如果有多个就取编号最小的那个）为 i，则 mn\[j\] > mx\[i\] 的那些肯定是要进前 A 大占位置的，而其他的点中 mx\[j\] > mx\[i\] 或 (mx\[j\] == mx\[i\] 且 j > i) 的就是可能被枚举进集合的。

考虑枚举出这个最小的 i，计算 mn\[j\] > mx\[i\]（即铁定进前 A 大的）的数量 fi 与 mn\[j\] <= mx\[i\] 且 (mx\[j\] > mx\[i\] 或 (mx\[j\] == mx\[i\] 且 j > i))（即可能枚举进集合的那些）的数量 gi。  
我们枚举从 gi 中选 j 个进入集合，则剩下的 b - j - 1 个就一定从 fi 中选，方案数为 \\(C\_\{g\_i\}^\{j\}\*C\_\{f\_i\}^\{b-j-1\}\\)。  
当然前提是 0 <= j <= gi 且 0 <= b - j - 1 <= fi 且 j + 1 + fi <= a。

## @accepted code@ ##

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 5000; const int MAXS = 2000000; const int MOD = int(1E9) + 7; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } vector<int>vec[MAXN + 5]; char str[MAXS + 5]; bool G[MAXN + 5][MAXN + 5]; int n, a, b; int tid[MAXN + 5], low[MAXN + 5], dcnt; int num[MAXN + 5], stk[MAXN + 5], tot, tp; int val[MAXN + 5]; void dfs(int x) { tid[x] = low[x] = (++dcnt), stk[++tp] = x; for(int i=1;i<=n;i++) if( G[x][i] ) { if( !tid[i] ) dfs(i), low[x] = min(low[x], low[i]); else if( !num[i] ) low[x] = min(low[x], tid[i]); } if( low[x] >= tid[x] ) { val[++tot] = 0; while( tp && tid[stk[tp]] >= tid[x] ) { int t = stk[tp--]; num[t] = tot, val[tot] = gcd(val[tot], vec[t].size()); } } } vector<int>v2[MAXN + 5]; int key[MAXN + 5]; bool tmp[MAXS + 5]; struct node{ int tr, mx; }nd[MAXN + 5]; int comb[MAXN + 5][MAXN + 5], f[MAXN + 5], g[MAXN + 5]; int solve() { for(int i=0;i<=n;i++) { comb[i][0] = 1; for(int j=1;j<=n;j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1])%MOD; } int ans = 0; for(int i=1;i<=n;i++) { f[i] = g[i] = 0; for(int j=1;j<=n;j++) { if( nd[j].tr > nd[i].mx ) f[i]++; else if( nd[j].mx > nd[i].mx || (nd[j].mx == nd[i].mx && j > i) ) g[i]++; } for(int j=0;j<=g[i];j++) if( b - j - 1 >= 0 && b - j - 1 <= f[i] && f[i] + j + 1 <= a ) ans = (ans + 1LL*comb[g[i]][j]*comb[f[i]][b-j-1])%MOD; } return ans; } int main() { scanf("%d%d%d", &n, &a, &b); for(int i=1;i<=n;i++) { scanf("%s", str + 1); for(int j=1;j<=n;j++) G[i][j] = str[j] - '0'; } for(int i=1;i<=n;i++) { int siz; scanf("%d%s", &siz, str); for(int j=0;j<siz;j++) vec[i].push_back(str[j] - '0'), nd[i].tr += (str[j] - '0'); } for(int i=1;i<=n;i++) if( !tid[i] ) dfs(i); for(int i=1;i<=tot;i++) for(int j=0;j<val[i];j++) v2[i].push_back(0); for(int i=1;i<=n;i++) for(int j=0;j<vec[i].size();j++) v2[num[i]][j%val[num[i]]] |= vec[i][j]; for(int i=tot;i>=2;i--) { int p = gcd(v2[i].size(), v2[i - 1].size()); for(int j=0;j<p;j++) tmp[j] = false; for(int j=0;j<v2[i].size();j++) tmp[j % p] |= v2[i][j]; for(int j=0;j<v2[i-1].size();j++) v2[i-1][j] |= tmp[j % p]; } for(int i=1;i<=tot;i++) for(int j=0;j<v2[i].size();j++) key[i] += v2[i][j]; for(int i=1;i<=n;i++) nd[i].mx = vec[i].size()/val[num[i]]*key[num[i]]; printf("%d\n", solve()); }

## @details@ ##

一开始把s1/s2\*g写成g\*s1/s2结果爆int。  
之后又因为tmp数组原本应该开成跟人数一样多结果开成了跟gang一个数据范围RE了一次。

在 tarjan 求强连通时，因为竞赛图本身的性质以及 tarjan 算法的性质，所以分配的强连通编号是按照拓扑序从大到小分配的。没有必要再来一遍拓扑排序。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11382208.html