LUANGAO高维网络

2017-08-07

高维网络

思路

如果数据范围不大的话可以考虑Dp

重编号降到一维,设DP[i]表示从A到i有多少步，转移不想写了，如果被割掉就赋成0，脑子在7kb以上应该都没问题…

然后对于如此巨大的数据范围，还是先骗分比较好…

如果p=0，可以知道路径数Ljs=(∑a[i])!/∑（a[i]!）（注意括号位置），所以如果没有隔断点的话，是可以用公式计算的，定义这个计算为sum（a，b），可以算出断点a—>断点b没有隔断点可以有多少种走法

那么就可以在断点上搞搞事

设f[i],表示从 A–>i 不经过任何一个断点的路径数，可以枚举走到这个点上一个断点是谁，那么可以算出sum(past,i),而走到past点有f[past]种走法，则在

sum(0,i)中有sum(past,i)*f[past]走法是至少经过了past这个不合法点的，同理，所有在i之前的点，都可以删除一些边，所以可得：

f[i]=sum(0,i)-∑(f[past]*sum(past,i))

岚后就DP出来了….

代码

#define mod 1000000007
#define ll long long
#define N 10000000
#include<iostream>
#include<cstdio>
#define P 505
#define D 105
using namespace std;
ll x1,y1,vis[P],f[P],x[P][D];
ll fac[N+10];
ll d,p;
bool can(ll a,ll b)
{
	if(a==b) return false;
	for(int i=1;i<=d;++i)
	{
		if(x[a][i]>x[b][i]) return false;
	}
	return true;
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	ll t=y;
	y=x-a/b*t;
	x=t;
}
ll sum(ll a,ll b)
{
	ll de[D];
	ll re=0;
	for(int i=1;i<=d;++i)
	{
        de[i]=x[b][i]-x[a][i];
	    re+=de[i];
	}
	re=fac[re];
	for(int i=1;i<=d;++i)
	{
		exgcd(fac[de[i]],mod,x1,y1);
		x1=(x1+mod)%mod;
		re=re*x1%mod;
	}
	return re;
}
ll dfs(ll n)
{
	if(vis[n]) return f[n];
	vis[n]=1;
	ll tot=sum(0,n);
	ll down=0;
	for(ll i=1;i<=p;++i)
	{
		if(can(i,n))
		{
			down+=dfs(i)*sum(i,n);
			down%=mod;
		}
	}
	f[n]=(tot-down+mod)%mod;
	return f[n];
}
int main()
{
//	freopen("cube.in","r",stdin);
//	freopen("cube.out","w",stdout);
	scanf("%d%d",&d,&p);
	for(int i=1;i<=d;++i) scanf("%d",&x[p+1][i]);
	for(int i=1;i<=p;++i)
	{
		for(int j=1;j<=d;++j)
		{
			scanf("%d",&x[i][j]);
		}
	}
	fac[0]=1;
	fac[1]=1;
	for(int i=2;i<=N;++i)
	fac[i]=fac[i-1]*i,fac[i]%=mod;
	printf("%d",dfs(p+1));
	return 0;
}
Comment Box
(update the code to your comment plugin in comment-full.html)