# Bzoj【省选模拟赛】

## 披着dfs外衣的计数DP

Posted by yjjr's blog on March 4, 2018

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

# 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;
{
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()
{