[NOIP2019模拟赛]HC1147 时空阵

￡神魔★判官ぃ 2023-06-01 06:08 43阅读 0赞

**题目描述：**

> 幽香这几天学习了魔法，准备建造一个大型的时空传送阵。
> 
> 幽香现在可以在幻想乡的n个地点建造一些传送门，如果她建造了从地点a与地点b之间的传送门，那么从a到b和从b到a都只需要单位1的时间。
> 
> 同时这些地点之间在地理上是非常遥远的，因此来往他们必须使用传送门。
> 
> 现在幽香想要问你，有多少种建造传送门的方案，使得地点1和地点n之间的最短距离恰好为k？两个方案不同当且仅当建造的传送门的集合不同。不能建造节点到自身的传送门，两个点之间也最多造一个传送门。

**分析：**

DP...

然而考场上没时间了，只打了20pts(k==1)

**　　为了防止变量名冲突，题面中的k在代码中都用m代替！！！**

首先：显然这道题的合法路径是一层一层的节点组成的

然后就可以DP了（话说考场上状态设计都设计出来了，转移没时间了...）

设f\[i\]\[j\]\[k\]表示当前进行到第i层，总共使用了j个节点，第i层使用了k个节点

显然这个可以有f\[i-1\]\[j-k\]\[s\]转移过来，我们只要枚举s就可以了，现在我们只要计算f\[i-1\]\[j-k\]\[s\]的系数就好了

分类讨论：

***当i<m时*:**

①可以当前层内部连边，也就是$2^\{C\_k^2\}$种可能

②当前层与上一层连边，且当前层的所有点至少有一条边连出去，也就是$(\\sum\\limits\_\{p=1\}^\{s\}C\_s^p-1)^k$

tip:上式子用二项式定理可以化简为$(2^\{s\}-1)^k$

③注意到当前这k个点是从剩下的n-j+k-1(最后减一是因为第n个点必须放在第m层)所以从这里面选k个点，方案数为$C\_\{n-j+k-1\}^k$

综上：$$f\[i\]\[j\]\[s\]=\\sum f\[i-1\]\[j-k\]\[s\]\*(2^s-1)^k\*C\_\{n-j+k-1\}^k\*C\_k^2$$

**　　　　当i==m时**

注意到只有第③个条件需要改变，也就是说第n个点肯定在这一层，所以只要在n-j+k-1中选择k-1的点即可，方案数为$C\_\{n-j+k-1\}^\{k-1\}$

即：$$f\[i\]\[j\]\[s\]=\\sum f\[i-1\]\[j-k\]\[s\]\*(2^s-1)^k\*C\_\{n-j+k-1\}^\{k-1\}\*C\_k^2$$

预处理一下组合数，及时取模，结合快速幂就好了

1 #include<bits/stdc++.h>
     2 #define int long long
     3 using namespace std;
     4 inline int read(){
     5     int ans=0,f=1;char chr=getchar();
     6     while(!isdigit(chr)){
        if(chr=='-')f=-1;chr=getchar();}
     7     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
     8     return ans*f;
     9 }const int P = 1e9+7;
    10 int n,m,f[105][105][105],ans,cc[105][105];
    11 int ksm(int x,int p){
    12     int ans=1;
    13     for(;p;p>>=1,x=x*x%P) if(p&1) ans=ans*x%P;
    14     return ans;
    15 }
    16 int C(int x,int y){
    17     int mul=1;
    18     for(int i=2;i<=y;i++) mul=mul*i%P;
    19     for(int i=2;i<=x-y;i++) mul=mul*i%P;
    20     int t=ksm(mul,P-2);
    21     mul=1;
    22     for(int i=2;i<=x;i++) mul=mul*i%P;
    23     mul=mul*t%P;
    24 }
    25 inline void Add(int &x,int y){x=x+y;if(x>=P)x-=P;}
    26 inline void Solve(){
    27     f[0][1][1]=1;
    28     for(int i=1;i<=m;++i)
    29         for(int j=1;j<=n;++j)
    30             for(int k=1;k<=j;k++){
    31                 for(int s=1;s<=j-k;s++)
    32                     if(i<m)//第一种 
    33                         Add(f[i][j][k],f[i-1][j-k][s]*ksm(2,(k-1)*k/2)%P*cc[n-j+k-1][k]%P*ksm(ksm(2,s)-1,k)%P);
    34                     else//第二种 
    35                         Add(f[i][j][k],f[i-1][j-k][s]*ksm(2,(k-1)*k/2)%P*cc[n-j+k-1][k-1]%P*ksm(ksm(2,s)-1,k)%P);
    36             }
    37     for(int i=m+1;i<=n;i++)
    38         for(int j=1;j<=n;j++)
    39             Add(ans,f[m][i][j]*ksm(2,(n-i)*(n-i-1)/2+j*(n-i)%P)%P);
    40     cout<<ans<<endl;
    41 }
    42 signed main(){
    43     freopen("timegate.in","r",stdin);
    44     freopen("timegate.out","w",stdout);
    45     for(int i=0;i<=100;i++)for(int j=0;j<=i;j++)cc[i][j]=C(i,j);//预处理组合数 
    46     n=read(),m=read();
    47     Solve();
    48     return 0;
    49 }

转载于:https://www.cnblogs.com/zhenglw/p/11342514.html