题目描述

这天S鮶正走在去机房的路上，无意间掉进了不知是哪位老人丢下的洞里，来到了隙间世界。

S鮶发现，隙间是一个p维空间，其中的点可以用一个p维坐标 (\(z_1\),\(z_2\),……\(z_p\)) 表示，且所有坐标的范围为\([1,n]\) 之间的整数，S鮶她的出发位置在\((1,1,……,1)\)。

隙间太大了，所以在任意两个点之间移动都要开坦克。S鮶一共有 \(m\) 架坦克，第 \(i\) 架坦克有两个值 \(a_i,b_i\) ，若这架坦克可以在两个点之间移动，则这两个点有 \(p-1\) 维坐标相同，且剩下一维坐标分别为 \(a_i,b_i\)。

但因为隙间太大了，S鮶算不出了出口在哪里，只算得该点的坐标的第 \(i\) 维 \(z_i\) 可能是 \(c_i\) 或者 \(1\)。于是S鮶想要知道有多少种刚好移动 \(q\) 次的方案，可以到达一个可能是出口的位置。

答案对 \(998244353\) 取膜。

输入格式

第一行4 个整数 \(n,m,p,q\)

第二行 \(p\) 个数 \(c_i\)

接下来 \(m\) 行每行两个数 \(a_i,b_i\)

输出格式

一个数表示答案

样例数据

input1

2 1 2 2
2 2
1 2

output1

4

input2

2 1 3 3
2 1 1
1 2

output2

7

样例解释

样例1

4 个位置都有可能是别墅的位置，到达(1, 1) 的方案有2 种，到达(2, 1) 的方案有0 种，到达(1, 2) 的方案有0 种，到达(2, 2) 的方案有2种，总方案数为4。

样例2

(1, 1, 1) 和(2, 1, 1) 可能是别墅的位置，到达(1, 1, 1) 的方案有0 种，到达(2, 1, 1) 的方案有7 种，总方案数为7。

数据规模与约定

前10%的数据，满足\(q\leq 10 , p=2 , q\leq 3\)

另外20%的数据，满足\(n\leq 20 , p\leq 3\)

另外20%的数据，满足\(m=n-1\) 所有\(z_i=1\), 第\(i\)个\(a_i=i,b_i=i+1,p\leq 100\)

对于100%的数据，满足\(n\leq 50;m,q\leq 100;p\leq 10^{6}\)

时间限制：\(1\text{s}\)

空间限制：\(512\text{MB}\)

Solution

首先可以发现，每一维都是独立的，所以先求出到任何一维的每一个点的方案数。这个直接dp就好了，也没有什么悬念。我们把求出来的命名为\(dp[i][j]\)表示到了\(i\)点走了\(j\)步的方案。

下面类似于背包。设\(f[i][j]\)表示前\(i\)维，走\(j\)步的方案数。

\[f[i][j]=\sum \limits_{k=0}^{j} f[i-1][j-k]\times dp[1\ or\ c[i]][k]\]

但是这个真的对吗？

我们发现，先第一维走一步，然后第二维走一步，然后第一维再走一步与西安第一维走两步，然后第二维走一步是不同的方案。所以式子可能还要改一下。

\[f[i][j]=\sum \limits_{k=0}^{j} f[i-1][j-k]\times dp[1\ or\ c[i]][k] \times C_j^k\]

为什么还要再乘上一个\(C_j^k\)呢？我们可以抽象一下，一共有\(j\)步给你走，然后这一维可以从中选\(k\)步，所以就是套个组合数。

但是直接转移是\(O(pq^2)\)的，肯定会超时。既然是递推，那么一个显然的思路是用矩阵优化。但是这个转移式还跟\(i\)有关呢！更确切的说，是跟\(c[i]\)有关。发现\(c[i]<=n\)，而\(n\)只有\(50\)，所以以坐标的值分开来转移。所以我们成功优化成了\(O(nq^3\log p)\)。可是好像还是过不了！！！

发现
\[ \begin{align*} f[i][j]&=\sum \limits_{k=0}^{j} f[i-1][j-k]\times dp[1\ or\ c[i]][k] \times C_j^k\ &=\sum \limits_{k=0}^{j} f[i-1][j-k]\times dp[1\ or\ c[i]][k] \times \frac{j!}{k!(j-k)!}\ &=(\sum \limits_{k=0}^{j} \frac{f[i-1][j-k]\times dp[1\ or\ c[i]][k]}{k!(j-k)!} )\times j! \end{align*} \]
细心地同学可能已经发现，这个新式子其实就相当于是再用可重复的全排列对其进行转移！

不妨设
\[ \begin{align*} f'[i][j]&=\sum \limits_{k=0}^{j} \frac{f[i-1][j-k]\times dp[1\ or\ c[i]][k]}{k!(j-k)!}\ &=\sum \limits_{k=0}^{j} \frac{f'[i-1][j-k]\times (j-k)!\times dp[1\ or\ c[i]][k]}{k!(j-k)!}\ &=\sum \limits_{k=0}^{j} \frac{f'[i-1][j-k]\times dp[1\ or\ c[i]][k]}{k!}\\end{align*} \]
于是我们实现了一个奇迹，我们使得后面转移里面与\(f\)无关的部分，也与\(j\)无关！

于是我们画一下它的转移矩阵，发现这是一个循环矩阵！于是我们可以用\(O(q^2)\)实现矩阵乘法，从而这做到\(O(nq^2\log p)\)的复杂度。但是之前的式子就不可以，因为它的矩阵中的每一项还要跟\(j\)有关，不是循环矩阵！

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define REP(i,a,n) for(register int i=(a);i<=(n);++i)
#define PER(i,a,n) for(register int i=(a);i>=(n);--i)
#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)
template<typename A>inline void read(A&a){a=0;char c=0;int f=1;while(c<'0'||c>'9')(c=getchar())=='-'?f=-1:0;while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();f==-1?a=-a:0;}
char buf[30];template<typename A>inline void write(A a){if(a<0)putchar('-'),a=-a;int top=0;if(!a)buf[top=1]='0';while(a)buf[++top]=a%10+'0',a/=10;while(top)putchar(buf[top--]);}
typedef long long ll;typedef unsigned long long ull;
template<typename A,typename B>inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;}
template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}

const int N=50+7,M=100+7,P=1e6+7,MOD=998244353;
int n,m,p,q,x,y,now,pre,c[N],f[2][M],C[M][M],fac[M],inv[M],a[M],b[M],ans[M],u[M],v[M];
int dp[M][M],vis[M][M];

struct Edge{int to,ne;}g[M<<1];int head[N],tot;
inline void addedge(int x,int y){g[++tot].to=y;g[tot].ne=head[x];head[x]=tot;}

inline ll DP(int x,int y){
    if(y==0)return vis[x][y]=1,dp[x][y]=(x==1);if(vis[x][y])return dp[x][y];
    int &ans=dp[x][y];vis[x][y]=1;
    for(register int i=head[x];i;i=g[i].ne)
        ans+=DP(g[i].to,y-1),ans>=MOD?ans-=MOD:0;
    return ans;
}
inline void Make_DP_on_Graph(){dp[1][0]=1;for(register int j=1;j<=q;++j)for(register int i=1;i<=m;++i)(dp[u[i]][j]+=dp[v[i]][j-1])%=MOD,(dp[v[i]][j]+=dp[u[i]][j-1])%=MOD;}
inline void Make_fac(){
    fac[0]=1;for(register int i=1;i<=q;++i)fac[i]=((ll)fac[i-1]*i)%MOD;
    inv[1]=1;for(register int i=2;i<=q;++i)inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    inv[0]=1;for(register int i=1;i<=q;++i)inv[i]=(ll)inv[i-1]*inv[i]%MOD;
} 

inline void Mul(int *p){
    memset(b,0,sizeof(b));
    for(register int i=0;i<=q;++i){
        int s=0;
        for(register int j=0;j<=i;++j)s+=(ll)a[j]*p[i-j]%MOD,s>=MOD?s-=MOD:0;
        b[i]=s;
    }
    memcpy(p,b,sizeof(b));
}

int main(){
//  freopen("camp.in","r",stdin);freopen("camp.out","w",stdout);
    read(n),read(m),read(p),read(q);
    for(register int i=1;i<=p;++i)read(x),++c[x];
    for(register int i=1;i<=m;++i)read(u[i]),read(v[i]);//错误笔记： 一开始以为重边只能算一个方案，没想到算不同的方案，导致考场丢了30分 
    Make_DP_on_Graph();Make_fac();ans[0]=1;
    for(register int i=1;i<=n;++i)if(c[i]){
        memset(a,0,sizeof(a));
        for(register int j=0;j<=q;++j)a[j]=ll(dp[1][j]+(i==1?0:dp[i][j]))*inv[j]%MOD;
        for(register int j=c[i];j;j>>=1,Mul(a))if(j&1)Mul(ans);
    }write((ll)ans[q]*fac[q]%MOD),putchar('\n');
    fclose(stdin);fclose(stdout);return 0;
}

[校内NOIP2018模拟20181020] wph AKIOI稳了

原文：https://www.cnblogs.com/hankeke/p/9830530.html