CF1153F Serval and Bonus Problem

    • 52通过
    • 67提交
  • 题目来源 CodeForces 1153F
  • 评测方式 RemoteJudge
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    有一段长为$l$的线段,有$n$个区间,左右端点在$[0,l)$间均匀随机(可能不是整数)

    求期望被至少$k$段区间覆盖的长度,对998244353取膜

    题目描述

    Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length of a random subsegment of a given segment. Then he left a bonus problem as homework, with the award of a garage kit from IOI. The bonus is to extend this problem to the general case as follows.

    You are given a segment with length $ l $ . We randomly choose $ n $ segments by choosing two points (maybe with non-integer coordinates) from the given segment equiprobably and the interval between the two points forms a segment. You are given the number of random segments $ n $ , and another integer $ k $ . The $ 2n $ endpoints of the chosen segments split the segment into $ (2n+1) $ intervals. Your task is to calculate the expected total length of those intervals that are covered by at least $ k $ segments of the $ n $ random segments.

    You should find the answer modulo $ 998244353 $ .

    输入输出格式

    输入格式:

    First line contains three space-separated positive integers $ n $ , $ k $ and $ l $ ( $ 1\leq k \leq n \leq 2000 $ , $ 1\leq l\leq 10^9 $ ).

    输出格式:

    Output one integer — the expected total length of all the intervals covered by at least $ k $ segments of the $ n $ random segments modulo $ 998244353 $ .

    Formally, let $ M = 998244353 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output such an integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .

    输入输出样例

    输入样例#1: 复制
    1 1 1
    
    输出样例#1: 复制
    332748118
    
    输入样例#2: 复制
    6 2 1
    
    输出样例#2: 复制
    760234711
    
    输入样例#3: 复制
    7 5 3
    
    输出样例#3: 复制
    223383352
    
    输入样例#4: 复制
    97 31 9984524
    
    输出样例#4: 复制
    267137618
    

    说明

    In the first example, the expected total length is $ \int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3} $ , and $ 3^{-1} $ modulo $ 998244353 $ is $ 332748118 $ .

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