永恒(Eternity)

Luogu
IDLGP10707
Time4000ms
Memory512MB
DifficultyP6
一些前置定义: - 可重集中的元素必须是非负整数。 - 可重集的大小为可重集中元素的个数。 - 对于一个大小为 $x$ 的可重集,设其中的元素为 $a_1,a_2\dots a_x$,那么这个可重集的**权值**就为 $a_1\oplus a_2\oplus \dots \oplus a_x$,即可重集中所有元素的**异或和**。 现在给出 $n,m$。 问有多少不同的大小为 $n$ 的可重集 $S$ 满足: $$\max\limits_{T \subseteq S,T\ne \emptyset}{Q_T}=m$$ 其中 $Q_T$ 为可重集 $T$ 的**权值**。 **注意:根据可重集的性质,数字相同但数字顺序不同的可重集算同一种可重集,即 $\left \{ 1,2,3 \right \} $ 与 $\left \{ 3,2,1 \right \} $ 算同一种可重集。** 求出不同可重集的个数 $\bmod\ 998244353$ 的结果。 可以证明这样的可重集个数是有限的。 ## Input 第一行两个整数,分别表示 $n$ 和 $m$。 ## Output 一行一个整数,表示答案对 $998244353$ 取模后的结果。 [samples] ## Background >$$行走人间的,$$ > >$$不一定是天使。$$ > >$$带来灾厄的,$$ > >$$不一定是恶魔。$$ > >$$恶魔的眼泪被天使珍藏 , $$ > >$$天使的纯净由恶魔守护。$$ > >$$或许,$$ > >$$这是最好的结局。$$ ## Note #### 【样例解释】 样例一中 $13$ 种方案分别为: $$(0,0,5)$$,$$(0,1,4)$$,$$(0,1,5)$$,$$(0,4,5)$$,$$(0,5,5)$$,$$(1,1,4)$$,$$(1,1,5)$$,$$(1,4,4)$$,$$(1,4,5)$$,$$(1,5,5)$$,$$(4,4,5)$$,$$(4,5,5)$$,$$(5,5,5)$$。 #### 【数据范围】 | subtask 编号 | $n$ | $m$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :-----: | | $0$ | $\le 10$ | $\le 10$ | $-$ | $10$ | | $1$ | $\le 10^5$ | $<2^{60}$ | $A$ | $20$ | | $2$ | $\le 2000$ | $\le 2000$ | $-$ | $10$ | | $3$ | $\le 10^5$ | $<2^{60}$ | $-$ | $60$ | 特殊性质 $A$: $\operatorname{popcount}(m)\le 5\ $,$\operatorname{popcount}(m)$ 表示 $m$ 的二进制表示中 $1$ 的个数。 对于 $100\%$ 的数据保证 $1\le n\le 10^5$,$0\le m<2^{60}$。 **特别提醒:本题使用 subtask 捆绑测试,只有通过一个子任务的全部测试点才能获得此子任务的分数。**
Samples
Input #1
3 5
Output #1
13
Input #2
12 7
Output #2
48643
API Response (JSON)
{
  "problem": {
    "name": "永恒(Eternity)",
    "description": {
      "content": "一些前置定义: - 可重集中的元素必须是非负整数。 - 可重集的大小为可重集中元素的个数。 - 对于一个大小为 $x$ 的可重集,设其中的元素为 $a_1,a_2\\dots a_x$,那么这个可重集的**权值**就为 $a_1\\oplus a_2\\oplus \\dots \\oplus a_x$,即可重集中所有元素的**异或和**。 现在给出 $n,m$。 问有多少不同的大小为 $n$ 的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10707"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一些前置定义:\n\n- 可重集中的元素必须是非负整数。\n\n- 可重集的大小为可重集中元素的个数。\n\n- 对于一个大小为 $x$ 的可重集,设其中的元素为 $a_1,a_2\\dots a_x$,那么这个可重集的**权值**就为 $a_1\\oplus a_2\\oplus \\dots \\oplus a_x$,即可重集中所有元素的**异或和**。\n\n现在给出 $n,m$。\n\n问有多少不同的大小为 $n$ 的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments