CF1093F Vasya and Array

    • 43通过
    • 69提交
  • 题目来源 CodeForces 1093F
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给出一段长度为 $n$ 的整数序列,一个正整数 $k$ ,一个正整数 $len$ ,序列中的所有数均在 $1$ ~$k$ 之间,或者等于 $-1$。

    如果没有长度大于 $len$ 的连续相同数字则该数段是好的。

    可以将 $-1$ 改为所有 $1$ ~$k$ 之间的整数,将该数列变为好的,求出方案数,对 $998244353$ 取模

    题目描述

    Vasya has got an array consisting of $ n $ integers, and two integers $ k $ and $ len $ in addition. All numbers in the array are either between $ 1 $ and $ k $ (inclusive), or equal to $ -1 $ . The array is good if there is no segment of $ len $ consecutive equal numbers.

    Vasya will replace each $ -1 $ with some number from $ 1 $ to $ k $ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $ 998244353 $ .

    输入输出格式

    输入格式:

    The first line contains three integers $ n, k $ and $ len $ ( $ 1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n $ ).

    The second line contains $ n $ numbers — the array. Each number is either $ -1 $ or between $ 1 $ and $ k $ (inclusive).

    输出格式:

    Print one integer — the number of ways to replace each $ -1 $ with some number from $ 1 $ to $ k $ (inclusive) so the array is good. The answer may be large, so print it modulo $ 998244353 $ .

    输入输出样例

    输入样例#1: 复制
    5 2 3
    1 -1 1 -1 2
    
    输出样例#1: 复制
    2
    
    输入样例#2: 复制
    6 3 2
    1 1 -1 -1 -1 -1
    
    输出样例#2: 复制
    0
    
    输入样例#3: 复制
    10 42 7
    -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
    
    输出样例#3: 复制
    645711643
    

    说明

    Possible answers in the first test:

    1. $ [1, 2, 1, 1, 2] $ ;
    2. $ [1, 2, 1, 2, 2] $ .

    There is no way to make the array good in the second test, since first two elements are equal.

    There are too many answers in the third test, so we won't describe any of them.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。