【DP】【强联通分量】【组合数学】CodeForces804F Fake bullions

分析：

首先，观察$i\%s_u=i\%s_v$这两个条件，无非就是说，对于u组中，某个拥有金块的人x，则所有v组中，满足$x\equiv y(mod(s_u,s_v))$ 的所有y都可以得到一个假的金块。

由于这个贡献是可以传递的，那么在一个强联通分量中，由于其能到达任意一个内部的点，所以如果某组第x个人有金块，那么最终所有满足$x\equiv y(mod(s_1,s_2,s_3,\dots \dots s_{tot}))$的所有人都可以有金块。

所以，可以先缩点，然后得到每个强联通分量内部的金块拥有情况，然后按照拓扑序算贡献即可。这里有个技巧：由于给出的图是个竞赛图，那么对于拓扑序中第i个点，那么必然有一条从i-1到i的边。

最后，就可以得到每组卖出金块的最大和最小数量。

然后就是组合数学的部分了：
对每种方案，把其按照金条数最小的一组来分类。

那么枚举每一组，假设其被选出且数量最小，那么只需要从比它大的数中选出剩下b-1个即可。

为了避免重复计算，这里重新定义了大小关系：
组A比组B大，则满足$(ma{x}_A>ma{x}_B)$或$(ma{x}_A=ma{x}_B且A>B)$

具体实现请参考代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 5010
#define MAXM 1000010
#define MOD 1000000007
using namespace std;
typedef long long ll;
vector<int> a[MAXN];
int n,A,B,cnt;
char s[MAXM];
int num[MAXN];
vector<int>gold[MAXN],tgold[MAXN];
int gcdv[MAXN];
int dfn[MAXN],low[MAXN],st[MAXN],top,nq[MAXN];
int gcd(int x,int y){
    if(y==0)return x;return gcd(y,x%y);	
}
char w[MAXN][MAXN];
int tot;
void tar(int x){
    dfn[x]=low[x]=++cnt;st[++top]=x;for(int u=0;u<n;u++){
    if(w[x][u]=='0')continue;
// PF("<%d -> %d>\n",x,u);if(dfn[u]==0){
    tar(u);low[x]=min(low[x],low[u]);}else if(nq[u]==0)low[x]=min(low[x],dfn[u]);}if(dfn[x]==low[x]){
    nq[x]=++tot;gcdv[tot]=num[x];while(st[top]!=x){
    nq[st[top]]=tot;gcdv[tot]=gcd(gcdv[tot],num[st[top]]);top--;}tgold[tot].resize(gcdv[tot]);top--;}
}
int totg[MAXN],mx[MAXN],mn[MAXN],fac[MAXN],inv[MAXN];
ll C(int x,int y){
    return (ll)fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
int main(){
    SF("%d%d%d",&n,&A,&B);for(int i=0;i<n;i++)SF("%s",w[i]);for(int i=0;i<n;i++){
    SF("%d",&num[i]);SF("%s",s);for(int j=0;j<num[i];j++)gold[i].push_back(s[j]-'0');}for(int i=0;i<n;i++)if(dfn[i]==0)tar(i);for(int i=0;i<n;i++)for(int j=0;j<num[i];j++)tgold[nq[i]][j%gcdv[nq[i]]]|=gold[i][j];for(int i=tot;i>1;i--){
    int now=gcd(gcdv[i],gcdv[i-1]);for(int j=0;j<gcdv[i];j++)tgold[i-1][j%now]|=tgold[i][j];}for(int i=1;i<=tot;i++)for(int j=0;j<gcdv[i];j++)if(tgold[i][j])totg[i]++;for(int i=0;i<n;i++){
    mx[i]=(ll)totg[nq[i]]*num[i]/gcdv[nq[i]];for(int j=0;j<num[i];j++)if(gold[i][j])mn[i]++;}fac[0]=1;
// for(int i=1;i<=tot;i++){
    
// for(int j=0;j<gcdv[i];j++)
// PF("%d",tgold[i][j]);
// PF("\n");
// }for(int i=1;i<=n;i++)fac[i]=(ll)fac[i-1]*i%MOD;inv[0]=inv[1]=1;for(int i=2;i<=n;i++)inv[i]=(ll)inv[MOD%i]*(MOD-MOD/i)%MOD;for(int i=2;i<=n;i++)inv[i]=(ll)inv[i-1]*inv[i]%MOD;int ans=0;
// for(int i=0;i<n;i++)
// PF("[%d %d]\n",mx[i],mn[i]);for(int i=0;i<n;i++){
    int c1=0,c2=0;for(int j=0;j<n;j++)if(mn[j]>mx[i])c1++;if(c1>=A)continue;	for(int j=0;j<n;j++)if(mn[j]<=mx[i]&&(mx[j]>mx[i]||(mx[j]==mx[i]&&j>i)))c2++;for(int j=min(B-1,min(c2,A-1-c1));B-j-1<=c1&&j>=0;j--)ans=(ans+(ll)C(c2,j)*C(c1,B-j-1)%MOD)%MOD;}PF("%d\n",ans);
}