NC212207. 旅行没有商问题
描述
我的歌曲只好向陌生的众人倾诉，
他们即使喝彩也会令我心伤，
当年赏识过我的歌诗的知音，
纵然在世亦不知向何方飘零。
——歌德《浮士德》
给出n个点，m条边的无向图。满足无重边、自环，不保证连通。某人在图上依次访问d个节点（即所经过的所有节点构成的序列长度为d）。n个点中有k个点必须至少经过一次。起点、终点任选。求满足条件的方案数对109+7取模的值
输入描述
第一行四个整数n，m，d，k，分别表示可选城市数量（图上点数），公路总数（无向边边数），旅游天数（访问节点个数），出题人想去的城市数量（必经节点个数）
第二行k个整数，表示出题人想去的各个城市的编号（各必经节点编号）
第三行到第m+2行，每行两个整数x，y，表示编号为x，y的城市之间修筑有一条公路（表示x，y两点间存在一条无向边）
输出描述
输出一个整数表示答案
示例1
输入:
4 5 4 2 1 2 1 2 1 3 2 3 2 4 3 4
输出:
36
说明:
合法方案（举例）：
3-1-2-4
3-1-2-3
2-3-1-3
非法方案（举例）：
4-1-2-3（4,1之间不存在边）
3-4-2-3（必经点1未被经过）
C++(clang++11) 解法, 执行用时: 157ms, 内存消耗: 400K, 提交时间: 2020-12-26 18:22:49
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
const int mod=1e9+7;
int n,m,d,p,i,j,k;
struct mat{
int a[24][24];
};
mat mul(mat x,mat y){
mat z;int i,j,k;rep(i,n)rep(j,n){
z.a[i][j]=0;rep(k,n)z.a[i][j]=(z.a[i][j]+x.a[i][k]*1ll*y.a[k][j])%mod;
}
return z;
}
mat pw(mat x,int y){
mat z;int i,j;rep(i,n)rep(j,n)z.a[i][j]=(i==j);
while(y){
if(y&1)z=mul(z,x);
y>>=1;x=mul(x,x);
}
return z;
}
int a[24],g[24][24],v[24];
int ans;
int main(){
cin>>n>>m>>d>>p;
for(i=0;i<p;i++){
cin>>a[i];
}
rep(i,m){
int x,y;cin>>x>>y;g[x][y]=g[y][x]=1;
}
for(i=0;i<(1<<p);i++){
rep(j,n)v[j]=1;
for(j=0;j<p;j++)if((i>>j)&1) v[a[j]]=0;
mat tmp;
rep(j,n)rep(k,n) tmp.a[j][k]=(g[j][k]&&v[j]&&v[k]);
tmp=pw(tmp,d-1);
int res=0;
rep(j,n)rep(k,n)if(v[j]&&v[k]) res=(res+tmp.a[j][k])%mod;
if(__builtin_popcount(i)&1) ans=(ans+mod-res)%mod; else (ans+=res)%=mod;
}
cout<<ans<<endl;
return 0;
}