← 返回题目列表

AtCoder · agc046_c

C. 移位

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给定的是一个字符串 S 组成 0 和 1。求字符串的数量,取模 998244353,可以通过对 S 之间 0 和 K 次(含):

  • 选择一对整数 分别为 i, j (1\leq i < j\leq |S|) 这样 i-th 和 j- 第一个字符 S 是 0 和 1。删除 j- 第一个字符 S 并将其插入到紧邻的左侧 i- 第一个字符。

约束

  • 1 \leq |S| \leq 300
  • 0 \leq K \leq 10^9
  • S 包括 0 和 1.

输入

输入由标准输入按以下格式给出:

S K

输出

求字符串的数量,取模 998244353,这可以通过对 S 之间 0 和 K 次(含)。


示例输入 1

0101 1

示例输出 1

4

四弦, 0101, 0110, 1001,和 1010,可以得到结果。


示例输入 2

01100110 2

示例输出 2

14

示例输入 3

1101010010101101110111100011011111011000111101110101010010101010101 20

示例输出 3

113434815