Bzoj【省选模拟赛】

披着dfs外衣的计数DP

Posted by yjjr's blog on March 4, 2018

标签:DP

题目

这里写图片描述

n,k<=12,L<=1e9

分析

设dis[i]表示1->i最短路

对于一条边的两个端点i,j,如果dis[i]==dis[j],那么这条边边权任意,同理,如果dis[i] < dis[j],那么边权不能小于dis[j]-dis[i]

同时对于点i,一定存在一个点j,使得dis[j] < dis[i]且j到i的边长度为dis[i]-dis[j]

我们可以将它们按照dis值从小到大排序,就可以直接进行dp

我们注意到一定会存在dis[1]=0,dis[n]=k

对于dis[i] > k的值,对答案无影响,可以直接用k+1表示

对于2~n-1的点,我们也不需要它们具体的最短路是多少,我们只需要知道对于最短路是j的点的个数就可以了

这样我们就可以从小到大枚举所有点的最短路x,再枚举满足最短路是x的点的个数,并计算方案总数

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int mod=1e9+7;
int a[16],b[16],n,k,L,tmp=1,cnt,bit[16];
ll ans;
void dfs(int x,int y){
	if(x==k+1){
		if(y+2!=n&&k==L)return;
		cnt=0;
		rep(i,1,n)
			rep(j,1,a[i])b[++cnt]=i;
		b[++cnt]=k;
		rep(i,1,n-y-2)b[++cnt]=k+1;
		ll re=1;
		rep(i,1,cnt){
			ll s1=1,s2=1;
			rep(j,0,i-1)
				if(b[j]<b[i])s1=s1*(L-(b[i]-b[j])+1)%mod,s2=s2*(L-(b[i]-b[j]))%mod;
			if(b[i]<=k)re=re*(s1-s2+mod)%mod;else re=re*s1%mod;
			rep(j,0,i-1)
				if(b[i]==b[j])re=re*L%mod;
		}
		int tt=tmp;rep(i,1,x-1)tt/=bit[a[i]];tt/=bit[n-y-2];
		ans=(ans+re*tt)%mod;return;
	}
	rep(i,0,n-y-2)a[x]=i,dfs(x+1,y+i);
}
int main()
{	
	n=read(),k=read(),L=read();
	bit[0]=1;rep(i,1,12)bit[i]=bit[i-1]*i;
	rep(i,2,n-2)tmp*=i;
	if(L<k){puts("0");return 0;}
	if(n==2){puts("1");return 0;}
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr