| 题目名称 | 2606. 欧拉图 |
|---|---|
| 输入输出 | euler.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 FoolMike
于2017-02-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：9， 通过率：100% | ||||
 AntiLeaf |
100 | 0.002 s | 0.29 MiB | C++ |
 stdafx.h |
100 | 0.110 s | 12.29 MiB | C++ |
|
AntiLeaf |
100 | 0.240 s | 29.81 MiB | C++ |
 FoolMike |
100 | 0.424 s | 31.14 MiB | C++ |
 宋逸群 |
100 | 0.454 s | 3.37 MiB | C++ |
 悸‘’ |
100 | 0.455 s | 31.14 MiB | C++ |
|
宋逸群 |
100 | 0.466 s | 3.37 MiB | C++ |
 czqqqaq |
100 | 0.526 s | 30.89 MiB | C++ |
 sxysxy |
100 | 0.527 s | 30.87 MiB | C++ |
| 关于 欧拉图 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @stdafx.h :
但是出题人没有考……所以暴力就好了 FoolMike
2017-02-21 20:37
5楼
| ||||
|
嗯。。。民白了，，
| ||||
|
这个有nlogn的多项式求逆做法
stdafx.h
2017-02-18 21:25
3楼
| ||||
|
回复 @Alboi_真神名曰蛋蛋 :
设F[i]表示含有i个点且每个点都是偶数度的方案数，将1号点取出，其他i-1个点之间任意连边，最后让奇数度的点与1连边，得到的图每个点的度数一定为偶数，因此有 F[i]=2^((i-2)*(i-1)/2) 设G[i]为含有i个点的欧拉图的个数，枚举1号点所在的联通块的点数j，通过容斥原理，我们有G[i]=F[i]-C[i-1][j-1]*F[i-j](1<=j<i) 由上述做法，我们得到了一个O(n^2)的算法 | ||||
|
$F(z)=\sum 2^{C_{n-1}^2} \frac{z^n}{n!}$
$G(z)=\sum g_n \frac{x^n}{n!}$ $ -> F(z)=G(z)*F(z)$ $ -> G(z)=1$ WTF !!!????!!  YGOI_真神名曰驴蛋蛋
2017-02-14 17:30
1楼
| ||||
【题目描述】
一个图如果我们可以通过去掉一条边、增加一条边或者保持不动变成欧拉图，我们称它为几乎欧拉图。
求n个点的几乎欧拉图有多少个，由于答案太大只需输出模10^9+7的答案即可。
【输入格式】
第一行一个整数n。
【输出格式】
一行一个整数，表示答案。
【样例输入】
42
【样例输出】
29010676
【提示】
对于30%的数据，2<=n<=10。
对于1OO%的数据，2<=n<=2000。
【来源】
2016河南省队集训，数据是Mike造的，谁有官测直接刷掉就好。