NC17521. [NOI2008]设计路线
描述
Z 国坐落于遥远而又神奇的东方半岛上，在小Z 的统治时代公路成为这里主要的交通手段。Z 国共有n 座城市，一些城市之间由双向的公路所连接。非常神奇的是Z 国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的城市直接通过公路相连。Z 国的首都是Z 国政治经济文化旅游的中心，每天都有成千上万的人从Z 国的其他城市涌向首都。
为了使Z 国的交通更加便利顺畅，小Z 决定在Z 国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。
我们定义每条规划路线为一个长度大于1 的城市序列，每个城市在该序列中最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有公共部分。
当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都。
我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数，而Z 国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明显首都的“不便利值”为0。小Z 想知道如何确定规划路线修建铁路使得Z 国的交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不便利值”达到最小。当然方案总数可能非常大，小Z 只关心这个天文数字mod Q 后的值。
注意：规划路线1-2-3 和规划路线3-2-1 是等价的，即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。
输入描述
第一行包含三个正整数N、M、Q，其中N 表示城市个数，M 表示公路总数，N 个城市从1~N 编号，其中编号为1 的是首都。Q 表示上文提到的设计路线的方法总数的模数。接下来M 行，每行两个不同的正数ai、bi (1≤ ai , bi ≤ N)表示有一条公路连接城市ai 和城市bi。 输入数据保证一条公路只出现一次。
输出描述
应包含两行。第一行为一个整数，表示最小的“不便利值”。 第二行为一个整数，表示使“不便利值”达到最小时不同的设计路线的方法总数 mod Q 的值。
如果某个城市无法到达首都，则输出两行-1。
示例1
输入:
5 4 100 1 2 4 5 1 3 4 1
输出:
1 10
说明:
以下样例中是10 种设计路线的方法：C++14(g++5.4) 解法, 执行用时: 280ms, 内存消耗: 64984K, 提交时间: 2019-08-20 21:49:16
#include<bits/stdc++.h>
#define FOG(x,y,z) for(register int x=y,x##_=z;x<=x##_;++x)
#define DOG(x,y,z) for(register int x=y,x##_=z;x>=x##_;--x)
#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)
#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)
#define ts (*this)
#define sf scanf
#define pf printf
#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)
using namespace std;
template<class T>bool tomin(T &x,T y){return y<x?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
char c;
x=0;
int f=1;
while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
do x=(x<<3)+(x<<1)+(c^48);
while(c=getchar(),c>='0'&&c<='9');
x*=f;
}
const db Pi=acos(-1);
const int maxn=1e5+5;
int n,m,P;
struct Edge{
int e,to;
}edge[maxn<<1];
int head[maxn],tot;
void Add(int x,int y){
edge[++tot]=(Edge){y,head[x]};
head[x]=tot;
}
namespace solve1{
int dis[maxn][2],Mx[maxn],L[maxn],R[maxn];
void dfs(int u,int f){
int s=0;
dis[u][1]=dis[u][0]=2e9;
EOR(u,v)if(v!=f){
dfs(v,u);
++s;
L[s]=R[s]=Mx[v]+1;
}
L[0]=R[s+1]=0;
FOR(i,1,s)tomax(L[i],L[i-1]);
DOR(i,s,1)tomax(R[i],R[i+1]);
s=0;
EOR(u,v)if(v!=f){
++s;
tomin(dis[u][1],max3(dis[v][1],L[s-1],R[s+1]));
}
int res[2]={0};
s=0;
EOR(u,v)if(v!=f){
++s;
res[1]=min(max(res[1],Mx[v]+1),max(res[0],dis[v][1]));
res[0]=min(max(res[0],Mx[v]+1),max(L[s-1],dis[v][1]));
tomin(dis[u][0],max(res[1],R[s+1]));
}
if(!s)dis[u][1]=dis[u][0]=0;
Mx[u]=min(dis[u][0],dis[u][1]);
}
int solve(){
dfs(1,0);
return Mx[1];
}
}
namespace P100{
ll dp[maxn][20][4];
ll Mod(ll x){
return (x-1)%P+1;
}
void Mod(ll &x,ll y){
x+=y;
x=Mod(x);
}
void dfs(int u,int f){
FOR(d,0,m)dp[u][d][0]=1;
bool flag=1;
EOR(u,v)if(v!=f){
flag=0;
dfs(v,u);
FOR(i,0,m){
ll res1=i>0?Mod(dp[v][i-1][0]+dp[v][i-1][1]+dp[v][i-1][2]):0;
ll res2=Mod(dp[v][i][0]+dp[v][i][1]);
DOR(j,2,0){
dp[u][i][j]=Mod(dp[u][i][j]*res1);
if(j)Mod(dp[u][i][j],Mod(dp[u][i][j-1]*res2));
}
}
}
}
bool solve(){
m=log2(n)+1;
dfs(1,0);
FOR(i,0,m){
ll res=Mod(dp[1][i][0]+dp[1][i][1]+dp[1][i][2]);
if(res)return pf("%d\n%lld",i,res%P),1;
}
}
}
int main(){
srand(time(NULL));
read3(n,m,P);
if(n==1)pf("0\n1");
else if(m<n-1)pf("-1\n-1");
else{
int x,y;
FOR(i,2,n){
read2(x,y);
Add(x,y);
Add(y,x);
}
P100::solve();
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 188ms, 内存消耗: 12920K, 提交时间: 2019-03-16 15:24:26
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define MN 100005
#define MS 12
using namespace std;
struct edge{int nex,to;}e[MN<<1];
int n,m,mod,pin;
int hr[MN],f[MN][2][MS];
inline int read()
{
int n=0,f=1; char c=getchar();
while (c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while (c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();}
return n*f;
}
inline void rw(int& x,int y) {x+=y; if(x>mod)x-=mod;}
inline int modu(ll x) {return !x?0:(x-1)%mod+1;}
inline void ins(int x,int y) {e[++pin]=(edge){hr[x],y}; hr[x]=pin;}
void dfs(int x,int fat)
{
register int i,j,k;
int g[3][MS],h[3][MS+5];
memset(g,0,sizeof(g));
memset(h,0,sizeof(h));
g[0][0]=1;
for (i=hr[x];i;i=e[i].nex)
{
if (e[i].to==fat) continue;
dfs(e[i].to,x);
for (j=0;j<MS;++j)
for (k=0;k<MS;++k)
{
rw(h[2][max(j+1,k)],modu(1LL*g[2][k]*(f[e[i].to][0][j]+f[e[i].to][1][j])));
rw(h[2][max(j,k)],modu(1LL*g[1][k]*f[e[i].to][0][j]));
rw(h[1][max(j+1,k)],modu(1LL*g[1][k]*(f[e[i].to][0][j]+f[e[i].to][1][j])));
rw(h[1][max(j,k)],modu(1LL*g[0][k]*f[e[i].to][0][j]));
rw(h[0][max(j+1,k)],modu(1LL*g[0][k]*(f[e[i].to][0][j]+f[e[i].to][1][j])));
}
for (j=0;j<MS;++j)
g[0][j]=h[0][j],h[0][j]=0,
g[1][j]=h[1][j],h[1][j]=0,
g[2][j]=h[2][j],h[2][j]=0;
}
for (i=0;i<MS;++i)
f[x][0][i]=g[0][i],rw(f[x][0][i],g[1][i]),f[x][1][i]=g[2][i];
}
int main()
{
register int i,x,y;
n=read(); m=read(); mod=read();
if (m!=n-1) return 0*printf("-1\n-1");
for (i=1;i<=m;++i)
x=read(),y=read(),
ins(x,y),ins(y,x);
dfs(1,0);
for (i=0;i<MS;++i)
if (f[1][0][i]||f[1][1][i])
return 0*printf("%d\n%d",i,(f[1][0][i]+f[1][1][i])%mod);
}