#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 1000000007 #define sz(x) ((int)((x).size())) // #define int ll // #define N using namespace std; const int N=3005; bool vis[N][N]; int a[N][N]; int n,m; vector<pa>all; int tot,tot1; int fl[N],tt[N],fa[N]; int nxt[N][N]; inline int gf(int x) { while (x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } inline ll quickPower(ll x,ll y) { ll res=1; while (y) { if (y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res; } void dfs(int x,int y) { ++tot; tot1+=(x>y); vis[x][y]=1; if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x] ||tot==tt[x]*tt[y]) return; for (int i=1;i<=m;) { if (!vis[a[x][i]][a[y][i]]) { dfs(a[x][i],a[y][i]); if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x] ||tot==tt[x]*tt[y]) return; } i=min(nxt[x][i],nxt[y][i]); } } mt19937_64 rnd(time(0)); void BellaKira() { n=3000,m=3000; cin>>n>>m; for (int i=1;i<=m;i++) { poly now(n+1,0); for (int j=1;j<=n;j++) now[j]=j; for (int j=1;j<=100;j++) { int x=rnd()%n+1,y=rnd()%n+1; swap(now[x],now[y]); } for (int j=1;j<=n;j++) a[j][i]=now[j]; for (int j=1;j<=n;j++) cin>>a[j][i]; } for (int i=m;i>=1;i--) { for (int j=1;j<=n;j++) if (i==m||a[j][i]!=a[j][i+1]) nxt[j][i]=i+1; else nxt[j][i]=nxt[j][i+1]; } for (int i=1;i<=n;i++) fa[i]=i,tt[i]=1; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) { int x=j,y=a[j][i]; x=gf(x),y=gf(y); if (x!=y) tt[x]+=tt[y],fa[y]=x; } } for (int i=1;i<=n;i++) fl[i]=gf(i); for (int i=1;i<=n;i++) tt[i]=tt[fl[i]]; int ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j&&!vis[i][j]) { tot=tot1=0; dfs(i,j); ans=(ans+1ll*(tot-tot1)*tot1%mod*quickPower(tot,mod-2)%mod)%mod; } cout<<ans<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } /*list: 1.mod 998244353 or 1e9+7 or ??? 2.N 3.duipai shuju xingtai duoyidian ... */
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 | #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 1000000007 #define sz(x) ((int)((x).size())) // #define int ll // #define N using namespace std; const int N=3005; bool vis[N][N]; int a[N][N]; int n,m; vector<pa>all; int tot,tot1; int fl[N],tt[N],fa[N]; int nxt[N][N]; inline int gf(int x) { while (x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; } inline ll quickPower(ll x,ll y) { ll res=1; while (y) { if (y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res; } void dfs(int x,int y) { ++tot; tot1+=(x>y); vis[x][y]=1; if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x] ||tot==tt[x]*tt[y]) return; for (int i=1;i<=m;) { if (!vis[a[x][i]][a[y][i]]) { dfs(a[x][i],a[y][i]); if (fl[x]==fl[y]&&tot==(tt[x]-1)*tt[x] ||tot==tt[x]*tt[y]) return; } i=min(nxt[x][i],nxt[y][i]); } } mt19937_64 rnd(time(0)); void BellaKira() { n=3000,m=3000; cin>>n>>m; for (int i=1;i<=m;i++) { poly now(n+1,0); for (int j=1;j<=n;j++) now[j]=j; for (int j=1;j<=100;j++) { int x=rnd()%n+1,y=rnd()%n+1; swap(now[x],now[y]); } for (int j=1;j<=n;j++) a[j][i]=now[j]; for (int j=1;j<=n;j++) cin>>a[j][i]; } for (int i=m;i>=1;i--) { for (int j=1;j<=n;j++) if (i==m||a[j][i]!=a[j][i+1]) nxt[j][i]=i+1; else nxt[j][i]=nxt[j][i+1]; } for (int i=1;i<=n;i++) fa[i]=i,tt[i]=1; for (int i=1;i<=m;i++) { for (int j=1;j<=n;j++) { int x=j,y=a[j][i]; x=gf(x),y=gf(y); if (x!=y) tt[x]+=tt[y],fa[y]=x; } } for (int i=1;i<=n;i++) fl[i]=gf(i); for (int i=1;i<=n;i++) tt[i]=tt[fl[i]]; int ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j&&!vis[i][j]) { tot=tot1=0; dfs(i,j); ans=(ans+1ll*(tot-tot1)*tot1%mod*quickPower(tot,mod-2)%mod)%mod; } cout<<ans<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } } /*list: 1.mod 998244353 or 1e9+7 or ??? 2.N 3.duipai shuju xingtai duoyidian ... */ |