圆 - 题目 - QOJ.ac

#8635. 圆

统计

题目描述

现在有$n(\geq 3)$个白色的球串成了一个圆环，编号依次为$1,2,\cdots,n$，现在你需要把这些球都染黑，具体操作为：

等概率随机地选择一个之前从未选过的球（白球、黑球都可以）。
将该白球和它相邻的两个白球都染黑。
如果所有白球都染黑，那么结束。

求出染黑所有白球的期望步数，答案对998244353取模。

输入格式

从标准输入读入数据。

一行一个正整数$n$，表示白球的个数。

输出格式

输出到标准输出。

一行一个数字，表示期望步数，对998244353取模。

样例

输入

输出

样例解释

第一次操作后，只剩下一个白球。接下来，有两个黑球可以选择，一个白球可以选择，不管选哪一个都会染黑所有的球。

样例

输入

输出

499122179

解释

数据范围

对于$40\%$的数据，$n\leq 10$。

对于$100\%$的数据，$n\leq 5000$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.