[Codeforces VK Cup 2016 - Round 2][矩阵树定理][高斯消元][骗（满）分]G. Little Artem and Graph

53 阅读 0 评论 35 点赞

我是靠谱客的博主陶醉钢笔，最近开发中收集的这篇文章主要介绍[Codeforces VK Cup 2016 - Round 2][矩阵树定理][高斯消元][骗（满）分]G. Little Artem and Graph，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

首先暴力上矩阵树定理加高斯消元是要T的
因为k+1~n的每个点只会向比它小的点连边，那么倒消元，每个方程就只要消最多k个元，这样复杂度就很小了……

不过这种做法被Manchery叉掉了……所以只能加个骗分的标签

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#define N 10010
#define P 1000000007

using namespace std;

typedef map<int,int>::iterator itr;

int n,k;
int d[N];
map<int,int> A[N];

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void rea(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline int Pow(int x,int y){
  int ret=1;
  for(;y;y>>=1,x=1ll*x*x%P) if(y&1) ret=1ll*ret*x%P;
  return ret;
}

inline int inv(int x){
  return Pow(x,P-2);
}

inline void gauss(int x,int y){
  int now=1ll*inv(A[x][x])*A[y][x]%P;
  for(itr i=A[x].begin();i!=A[x].end();i++)
    if(i->first<n)
      (A[y][i->first]+=P-1ll*now*A[x][i->first]%P)%=P;
  int cnt=0;
  for(itr i=A[y].begin();i!=A[y].end();i++)
    if(i->first<n&&!(i->second)) d[++cnt]=i->first;
  for(int i=1;i<=cnt;i++) A[y].erase(A[y].find(d[i]));
}

inline int det(){
  for(int i=1;i<n;i++)
    for(itr j=A[i].begin();j!=A[i].end();j++)
      if(j->first!=i&&j->first<n) gauss(i,j->first);
  int ret=1;
  for(int i=1;i<n;i++) ret=1ll*ret*A[i][i]%P;
  return ret;
}

int main(){
  rea(n); rea(k);
  for(int i=n-k;i;i--)
    for(int j=1;j<=k;j++){
      int x; rea(x); x=n-x+1;
      A[i][x]=A[x][i]=P-1;
      A[i][i]++; A[x][x]++;
    }
  for(int i=n-k+1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
      A[i][j]=A[j][i]=P-1,A[i][i]++,A[j][j]++;
  return printf("%dn",det()),0;
}