| 题目名称 | 2359. [HZOI 2015] QAQ的图论题 |
|---|---|
| 输入输出 | QAQ_Graph.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-06-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：27， 提交：59， 通过率：45.76% | ||||
 FoolMike |
100 | 0.638 s | 8.29 MiB | C++ |
 ztzshiwo |
100 | 0.831 s | 10.31 MiB | C++ |
|
ztzshiwo |
100 | 0.851 s | 10.31 MiB | C++ |
 Aglove |
100 | 0.897 s | 7.18 MiB | C++ |
 Gintoki |
100 | 0.902 s | 11.73 MiB | C++ |
|
Gintoki |
100 | 0.904 s | 11.73 MiB | C++ |
 __debug |
100 | 0.918 s | 7.32 MiB | C++ |
 sherco |
100 | 0.963 s | 9.06 MiB | C++ |
 assassain |
100 | 0.985 s | 9.83 MiB | C++ |
 jefflyy |
100 | 1.145 s | 5.29 MiB | C++ |
| 本题关联比赛 | |||
| noi2017模板练习+ | |||
| 关于 QAQ的图论题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
题解戳http://www.cnblogs.com/joyouth/p/5599564.html
Aglove
2016-06-20 09:08
1楼
| ||||
【题目描述】
QAQ喜欢玩无向简单图(简单图即图中无自环无重边)
定义函数$F(V,E)$表示一个图的价值，$F(V,E)=\sum\limits_{i=1}^{n}deg(i)^k$
也就是这个图的每个点的度数的$k$次方的和
为了方便计算，我们定义$0^0=1$
现在QAQ想要知道$n$个点的所有可能的无向简单的图的价值和是多少
由于答案可能很大，所以要求你对$998244353$取模后输出
【输入格式】
第一行输入$n，k$如题意所示
【输出格式】
输出相应的答案
【样例输入】
3 2
【样例输出】
36
【提示】
样例解释：
不难发现一共有$8$种情况，我们用一个三元组$(a,b,c)$表示$(1-2,2-3,3-1)$的边的状态
1、$(0,0,0)$ 价值为$0$
2、$(1,0,0)$ 价值为$1^2+1^2=2$
3、$(0,1,0)$ 价值为$1^2+1^2=2$
4、$(0,0,1)$ 价值为$1^2+1^2=2$
5、$(1,1,0)$ 价值为$1^2+2^2+1^2=6$
6、$(1,0,1)$ 价值同上也是$6$
7、$(0,1,1)$ 价值同上也是$6$
8、$(1,1,1)$ 价值为$2^2+2^2+2^2=12$
所以总和为$36$
对于10%的数据，$n<=5$
对于另外10%的数据，$k=0$
对于另外10%的数据，$k=1$
对于另外20%的数据，$n<=10^5$
对于另外20%的数据，$k<=10^3$
对于100%的数据，$n<=10^9,k<=10^5$