BZOJ 3776:警察署
3123 ワード
どうして3776またテーマを変えましたか...テーマを変えました...テーマを変えました...目が覚めました...
SCCがポイントダウンした後、入度または出度が0の点だけ警察署に行かなければなりません
合計t-1入度または出度0のSCCがあると仮定する
q[1]-q[t-1]はこれらのSCC中点の個数を表す
q[t]は残りの点の個数を表す
f[i][j]=sum(f[i-1][j-x]*C[q[i]][x])
時間複雑度$O(n^2)$
SCCがポイントダウンした後、入度または出度が0の点だけ警察署に行かなければなりません
合計t-1入度または出度0のSCCがあると仮定する
q[1]-q[t-1]はこれらのSCC中点の個数を表す
q[t]は残りの点の個数を表す
f[i][j]=sum(f[i-1][j-x]*C[q[i]][x])
時間複雑度$O(n^2)$
#include<cstdio>
const int N=105,M=20010,B=10000,MAXL=9;
int T,n,m,i,j,k,x,ans[N],g[2][N],nxt[2][M],v[2][M],ed,fa[N],d[2][N],q[N],t,s[N];bool vis[N];
struct Num{
int a[MAXL],len;
Num(){len=1,a[1]=0;}
inline Num operator+(Num b){
Num c;
c.len=(len>b.len?len:b.len)+2;
int i;
for(i=1;i<=c.len;i++)c.a[i]=0;
for(i=1;i<=len;i++)c.a[i]=a[i];
for(i=1;i<=b.len;i++)c.a[i]+=b.a[i];
for(i=1;i<=c.len;i++)if(c.a[i]>=B)c.a[i+1]++,c.a[i]-=B;
while(c.len>1&&!c.a[c.len])c.len--;
return c;
}
inline void operator+=(Num b){*this=*this+b;}
inline Num operator*(Num b){
Num c;
c.len=len+b.len+2;
int i,j;
for(i=1;i<=c.len;i++)c.a[i]=0;
for(i=1;i<=len;i++)for(j=1;j<=b.len;j++){
c.a[i+j-1]+=a[i]*b.a[j];
if(c.a[i+j-1]>=B){
c.a[i+j]+=c.a[i+j-1]/B;c.a[i+j-1]%=B;
if(c.a[i+j]>=B)c.a[i+j+1]+=c.a[i+j]/B,c.a[i+j]%=B;
}
}
while(c.len>1&&!c.a[c.len])c.len--;
return c;
}
void write(){
printf("%d",a[len]);
for(int i=len-1;i;i--)printf("%04d",a[i]);
puts("");
}
}one,C[N][N],f[N][N];
inline void read(int&a){char ch;while(!(((ch=getchar())>='0')&&(ch<='9')));a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';}
inline void add(int x,int y){
v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed;
v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;
}
void dfs1(int x){
vis[x]=1;
for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]);
q[++t]=x;
}
void dfs2(int x,int y){
vis[x]=0,fa[x]=y,s[y]++;
for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y);
}
void work(){
for(ed=0,i=1;i<=n;i++)g[0][i]=g[1][i]=g[2][i]=d[0][i]=d[1][i]=s[i]=vis[i]=0;
read(n),read(m),read(k);
while(m--)read(i),read(j),add(i,j);
for(t=0,i=1;i<=n;i++)if(!vis[i])dfs1(i);
for(i=n;i;i--)if(vis[q[i]])dfs2(q[i],q[i]);
for(i=1;i<=n;i++)for(j=g[0][i];j;j=nxt[0][j])if(fa[i]!=fa[v[0][j]])d[0][fa[i]]++,d[1][fa[v[0][j]]]++;
for(i=1,t=0;i<=n;i++)if(fa[i]==i&&(!d[0][i]||!d[1][i]))q[++t]=s[i];
for(i=1,q[++t]=0;i<=n;i++)if(fa[i]==i&&d[0][i]&&d[1][i])q[t]+=s[i];
for(i=1;i<t;i++)for(j=0;j<=k;j++){
f[i][j]=Num();
for(x=1;x<=q[i]&&x<=j;x++)f[i][j]+=f[i-1][j-x]*C[q[i]][x];
}
for(j=0;j<=k;j++){
f[t][j]=Num();
for(x=0;x<=q[t]&&x<=j;x++)f[t][j]+=f[t-1][j-x]*C[q[t]][x];
}
f[t][k].write();
}
int main(){
one.a[1]=1;
for(i=1,C[0][0]=f[0][0]=one;i<N;i++)for(j=1,C[i][0]=C[i][i]=one;j<i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
read(T);
while(T--)work();
return 0;
}