#N0411. 设计道路【NOIP2023模拟赛T1】

设计道路【NOIP2023模拟赛T1】

题目描述

小明在某个游戏中要设计一个公园。

这个公园可以看成是一幅nn个点,mm条有向边的简单有向无环图(没有重边,没有自环)。

小明指定11号点作为起点,nn号点作为终点。

小明的需求是:他需要让这幅图从起点到终点的方案数,恰好是KK种。

请帮助小明设计这样一幅图吧。

输入格式

输入一个参数KK

输出格式

首先输出n,mn,m,表示点数,边数。

请注意,你必须保证你输出的n91,m230n\leq 91,m\leq 230

然后输出mm行,每行u,v(1u<vn)u,v(1\leq u<v\leq n)表示一条有向边。

可以证明有向无环图一定存在一种编号方式满足,所有的边都是从编号小的连接到编号大的。

样例输入 #1

2

样例输出 #1

3 3
1 2
2 3
1 3

样例解释 #1

一共两条路:(1,2,3),(1,3)(1,2,3),(1,3)

样例输入 #2

3

样例输出 #2

4 5
1 2
2 3
3 4
1 3
2 4

样例解释 #2

一共三条路:(1,2,4),(1,2,3,4),(1,3,4)(1,2,4),(1,2,3,4),(1,3,4)

数据范围

请注意,你必须保证你输出的n91,m230n\leq 91,m\leq 230

对于10%的数据:K85K\leq 85

对于30%的数据:K<29K<2^9

对于50%的数据:K<230K<2^{30}

对于70%的数据:K<245K<2^{45}

对于80%的数据:K<246K<2^{46}

对于100%的数据:K<262K<2^{62}

以下是你可以用到的checker,出题人多么良心啊,给大家省去了宝贵的11分钟。

#include<bits/stdc++.h>
#define maxn 105
#define ll long long
using namespace std;
int n,m,u,v;
basic_string<int> edge[maxn];
ll dp[maxn];
map<int,int> vis;
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++) 
	{
		cin>>u>>v; 
		assert(u<v); assert(vis[u*177+v]==0); 
		vis[u*177+v]=1; edge[u]+=v;
	}
	dp[1]=1;
	for (int i=1;i<n;i++) for (int j:edge[i]) dp[j]+=dp[i];
	cout<<dp[n]<<endl;	
}