[AGM 2022 资格赛] 抛硬币

Luogu
IDLGP8229
Time1000ms
Memory256MB
DifficultyP5
2022O2优化AGM
伊利找到了一个魔法数字 $K$,一个装满草莓的魔法篮子,还有一个魔法硬币。 伊利注意到,当抛硬币时,它有 $P$ 的概率概率朝上。随后她抛了 $n$ 次硬币,如果硬币朝上篮子里的草莓会变成原来的 $K$ 倍。否则,她会吃掉篮子里的所有草莓,吃完后篮子会神奇地变出一颗新的草莓。 伊利现在很好奇她在抛 $n$ 次硬币后期望会吃多少草莓。请你告诉她答案在 $\bmod\ 998244353$ 意义下的答案。 ## Input 第一行一个数 $T$,表示数据组数。 接下来 $T$ 行,每一行三个数表示 $n,K,P$。 ## Output $T$ 行,每行一个正整数表示答案。 [samples] ## Note #### 数据规模与约定 对于 $100\%$ 的数据,满足 $1\leq T\leq 10^5$,$1\leq n \leq 10^{18}$,$0\leq K,P<998244353$。 #### 说明 翻译自 [AGM 2022 Qualification Round A CoinFlip](https://judge.agm-contest.com/public/problems/21/text)。
Samples
Input #1
4
1 2 499122177
3 2 499122177
10 2 499122177
1000000000000000000 100 16235235
Output #1
499122177
748683267
748683281
565383148
API Response (JSON)
{
  "problem": {
    "name": "[AGM 2022 资格赛] 抛硬币",
    "description": {
      "content": "伊利找到了一个魔法数字 $K$,一个装满草莓的魔法篮子,还有一个魔法硬币。 伊利注意到,当抛硬币时,它有 $P$ 的概率概率朝上。随后她抛了 $n$ 次硬币,如果硬币朝上篮子里的草莓会变成原来的 $K$ 倍。否则,她会吃掉篮子里的所有草莓,吃完后篮子会神奇地变出一颗新的草莓。 伊利现在很好奇她在抛 $n$ 次硬币后期望会吃多少草莓。请你告诉她答案在 $\\bmod\\ 998244353$ 意义下",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8229"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "伊利找到了一个魔法数字 $K$,一个装满草莓的魔法篮子,还有一个魔法硬币。\n\n伊利注意到,当抛硬币时,它有 $P$ 的概率概率朝上。随后她抛了 $n$ 次硬币,如果硬币朝上篮子里的草莓会变成原来的 $K$ 倍。否则,她会吃掉篮子里的所有草莓,吃完后篮子会神奇地变出一颗新的草莓。\n\n伊利现在很好奇她在抛 $n$ 次硬币后期望会吃多少草莓。请你告诉她答案在 $\\bmod\\ 998244353$ 意义下...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments