列表

详情

NC230852. Cards of Magic

描述

Raiden Shogun, the ruler of Inazuma, is playing a new card game invented by her friend Yae Miko.


Pixiv ID: 93716380

The player needs to defeat a monster of health point (HP) n by using magic cards properly.

Specifically, there are three kinds of magic cards:
  1. Waterman: Summon the Waterman on the field and the Waterman will stay on the field forever. Each time when you cast a magic card and the Waterman has been on the field, it will reduce the monster's HP by 1. Note that if you cast another Waterman card when the Waterman has already been on the field, nothing will happen except the monster's HP decresing by 1;
  2. Fireball: Reduce the monster's HP by 2;
  3. Copy: Copy any card casted before this card and receive a copy of the copied card.
At the beginning of each turn, the player receives a new card from one of the three kind in equal possibility of . Then the player can choose to cast some magic cards in his hand one by one and the casted cards will take effect respectively. Since there is no limitation for the number of cards in hand, the player can choose to keep cards and do nothing in the turn.

The monster will be defeated if its HP becomes nonpositive. Now Raiden Shogun hopes you can calculate the expected number of turns to defeat the monster if she plays optimally to minimize the expected number of turns.

输入描述

The only line contains a single integer n , indicating the monster's HP.

输出描述

Output a line containing an integer, indicating the expected number of turns to defeat the monster modulo  if playing optimally.

More precisely, if the reduced fraction of the answer is , what you should provide is the minimum nonnegative integer r such that . You may safely assume that such r always exists.

示例1

输入: 

1

输出: 

831870296

说明:

In the first sample case:
If receiving a Waterman card in the first turn, just cast it and the monster will be defeated no matter receiving which kind of magic card in the next turn;
If receiving a Fireball card in the first turn, just cast it and defeat the monster immediately;
If receiving a Copy card in the first turn, do nothing in the following turns until receiving a Waterman card or a Fireball card. Once receiving a Waterman card, the monster will be defeated by casting the Waterman card and then casting any card in hand. Once receiving a Fireball card, the monster will be defeated by casting the Fireball card immediately.
In all, the expected number of turns to defeat the monster of HP 1 is \frac{11}{6} if playing optimally.

示例2

输入: 

5

输出: 

835978299

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 60ms, 内存消耗: 33684K, 提交时间: 2021-11-29 09:15:29 

#include<bits/stdc++.h>
using namespace std;

const int mod = 998244353;
int n;

int iv[15];
int dp[300105][2][2][3];
bool vis[300105][2][2][3];

int getdp(int fire, int has, int water, int cpy) {
  if (vis[fire][has][water][cpy]) return dp[fire][has][water][cpy];
  vis[fire][has][water][cpy] = 1;
  if (water) {
    if ((cpy == 2) || (!has && fire + 2 * cpy >= n) || (has && 4 * cpy + fire >= n)) return dp[fire][has][water][cpy] = 1;
    int ans = (getdp(fire + 1, has, 1, cpy) + getdp(fire, has, 1, cpy + 1)) % mod;
    ans = (ans + getdp(fire + 3, 1, 1, cpy)) % mod;
    ans = 1ll * ans * iv[3] % mod;
    ans = (ans + 1) % mod;
    return dp[fire][has][water][cpy] = ans;
  }
  else {
    if (!has && (cpy * 2 + fire + 2 >= n) && cpy >= 2) return dp[fire][has][water][cpy] = 5ll * iv[2] % mod;
    if (has && (fire + cpy * 2 >= n)) return dp[fire][has][water][cpy] = 1;
    int ans = (getdp(fire + 2, 1, 0, cpy) + (cpy < 2 ? getdp(fire, has, 0, cpy + 1) : getdp(fire + 2, has, 0, 2))) % mod;
    ans = (ans + getdp(fire / 2 * 3, has, 1, cpy)) % mod;
    ans = 1ll * ans * iv[3] % mod;
    ans = (ans + 1) % mod;
    return dp[fire][has][water][cpy] = ans;
  }
}

signed main() {
  #ifdef Sakuyalove
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
  #endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  iv[1] = 1;
  for (int i = 2; i <= 10; i++) iv[i] = 1ll * (mod - mod / i) * iv[mod % i] % mod;
  cin >> n;
  cout << (getdp(0, 0, 0, 0) + mod - 1) % mod << endl;
  return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 18ms, 内存消耗: 2092K, 提交时间: 2022-11-09 16:44:00 

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

const int mo=998244353;
const int inv2=(mo+1)>>1;
const int inv3=(mo+1)/3; 

int jie[200005],inv[200005],n;

int C(int o,int p){return (o<p)?0:(1ll*jie[o]*inv[p]%mo*inv[o-p]%mo);}

int mi(int o,int p)
{
	int yu=1;
	while(p)
	{
		if(p&1) yu=1ll*yu*o%mo;
		o=1ll*o*o%mo;
		p>>=1;
	}
	return yu;
}

int main()
{
	jie[0]=1;
	for(int i=1;i<=200000;i++) jie[i]=1ll*jie[i-1]*i%mo;
	inv[200000]=mi(jie[200000],mo-2);
	for(int i=199999;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mo;
	scanf("%d",&n);
	int ans=1,cal=1,la=0;
	for(int i=1,fac=inv3;i<=n;i++,fac=1ll*fac*inv3%mo)
	{
		ans=(ans+1ll*fac*cal%mo)%mo;
		int yu=min(i,(n-i-1)>>1);
		cal=((cal+cal-C(i,la))%mo+mo)%mo;
		if(la>yu)
		{
			cal=(cal-C(i+1,la)+mo)%mo;
		}else
		if(la<yu)
		{
			cal=(cal+C(i+1,yu))%mo;
		}
		la=yu;
	}
	cal=3;la=1;
	for(int i=3,fac=1ll*inv3*inv3%mo*inv3%mo;i<=n-5;i++,fac=1ll*fac*inv3%mo)
	{
		ans=(ans+1ll*fac*i%mo*(cal-1)%mo)%mo;
		int yu=min(i-1,(n-i-4)>>1);
		cal=((cal+cal-C(i-1,la))%mo+mo)%mo;
		if(la>yu)
		{
			cal=(cal-C(i,la)+mo)%mo;
		}else
		if(la<yu)
		{
			cal=(cal+C(i,yu))%mo;
		}
		la=yu;
	}
	for(int i=2,fac=1ll*inv3*inv3%mo;i<=n-1;i++,fac=1ll*fac*inv3%mo)
	{
		ans=(ans+1ll*fac*i%mo)%mo;
	}
	for(int i=1,fac=inv3,cal=1;i<=(n-1)>>1;i++,fac=1ll*fac*inv3%mo,cal=(cal+cal+1)%mo)
	{
		ans=(ans+1ll*fac*cal%mo)%mo;		
	}
	ans=(ans+inv2)%mo;
	cout<<ans<<endl;
	return 0;
}

上一题

© 2025 nowcoder.com