【xsy1503】 fountain DP

题目大意：给你$D$个格子，有$n$个喷水器，每个喷水器有一个喷水距离$r_i$。

现在你需要在这$D$个格子中选择$n$个位置按照任意顺序安装这$n$个喷水器，需要满足$n$个喷水器互相喷不到对方。

问方案数，对$10^9+7$取模

数据范围：$n$,$r_i≤40$，$D≤10^5$

我们不妨考虑我们钦定了这$n$个喷水器的出现顺序，从左到右第$i$个喷水器编号为$p[i]$。

确定排列顺序后，令$d=\sum \limits_{i=1}^{n-1} max(r_{p[i]},r_{p[i+1]})$

我们发现上式累加的实际上是相邻两个喷水器之间的最小间隔

我们尝试把这个间隔中的格子看成是一个格子。

我们就可以把原序列中$D$个格子看成是$D-d-1$个了。

现在也就是变成了要在这剩下的格子之间插入这$n$个喷水器，方案数显然为$\binom{D-d-1+n}{n}$。

下面考虑如何求不同的排列顺序数量。

我们先将$n$个喷水器按照喷水半径进行排序。

设$f[i][j][k]$表示前i个喷水器必须出现，且这$i$个喷水器间（包括两端），有$j$个可以插入喷水器，且由这些喷水器累加出的$d$为$k$的方案数量。

下面考虑在$f[i][j][k]$的基础上插入第$i+1$个喷水器。

假定这个喷水器插入后，两侧不能再插入喷水器，则有$f[i+1][j-1][k+2r_{i+1}]+=f[i][j][k]\times (j-2)$

假定这个喷水器插入后，只有一侧能插入喷水器，则有$f[i+1][j][k+r_{i+1}]+=f[i][j][k]\times (2j-2)$

上面两个转移需要$-2$的原因显然（并不能允许最左侧和最右侧插入喷水器）

假定这个喷水器插入后，两侧皆可以插入喷水器，则有$f[i+1][j+1][k]+=f[i][j][k]\times j$

初始情况：$f[1][2][0]=1$，答案为$\sum \limits_{i=1}^{\infty} f[n][2][i]$

转移和答案统计的时候记得取模即可

时间复杂度：$O(n^2\sum \limits_{i=1}^{n} r_i)$

 #include<bits/stdc++.h>

 #define M 42

 #define N 110000

 #define L long long

 #define MOD 1000000007

 using namespace std;

 L pow_mod(L x,L k){L ans=; for(;k;k>>=,x=x*x%MOD) if(k&) ans=ans*x%MOD;  return ans;}

 L fac[N]={},invfac[N]={};

 L C(int n,int m){if(n-m<) return ; return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;}

 int n,D,r[M]={};

 L f[M][M][M*M]={};

 int main(){

     fac[]=; for(int i=;i<N;i++) fac[i]=fac[i-]*i%MOD;

     invfac[N-]=pow_mod(fac[N-],MOD-);

     for(int i=N-;~i;i--) invfac[i]=invfac[i+]*(i+)%MOD;

     scanf("%d%d",&n,&D);

     for(int i=;i<=n;i++) scanf("%d",r+i);

     sort(r+,r+n+);

     f[][][]=;

     for(int i=;i<n;i++)

     for(int j=;j<=n+;j++)

         for(int k=;k<M*M;k++)

         if(f[i][j][k]){

             (f[i+][j+][k]+=f[i][j][k]*j)%=MOD;

             if(j>) (f[i+][j-][k+*r[i+]]+=f[i][j][k]*(j-))%=MOD;

             if(j>) (f[i+][j][k+r[i+]]+=f[i][j][k]*(*j-))%=MOD;

         }

     L ans=;

     for(int d=;d<M*M;d++)

     if(f[n][][d]){

         (ans+=C(D-d-+n,n)*f[n][][d])%=MOD;

     }

     cout<<ans<<endl;

 }

巴特西

【xsy1503】 fountain DP

最新文章

热门文章