AT987 高橋君

    • 60通过
    • 115提交
  • 题目来源 AtCoder 987
  • 评测方式 RemoteJudge
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 6000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    **


    -- AT987 高桥君

    题目描述

    字符串S满足以下条件被称为符合高桥君要求的字符串;

    1.S是仅由0和1组成的字符串。

    2.S的长度为n。

    3.S最多包含k个1。

    输出时取模1000000007

    输入输出格式

    输入格式:

    以下为标准输入格式: $ T $

    $ n_1 $ $ k_1 $

    $ n_2 $ $ k_2 $

    ......

    $ n_T $ $ k_T $

    T为输入的字符串的数量,接下来的T行 每行给出高桥君要求的数 $ n_i $ , $ k_i$ 。

    输出格式: 符合高桥君要求的字符串的数量取模1000000007。

    ps:结尾需要换行符!!!

    题目描述

    文字列 $ S $ は、次の条件を満たすとき高橋君であるという。

    • $ S $ は、 0, 1のみからなる文字列である。
    • $ S $ の長さがちょうど $ n $ である。
    • $ S $ は高々 $ k $ 個の 1 を含む。

    高橋君の個数を $ 1000000007 $ で割った余りを求めよ。

    输入输出格式

    输入格式:

    入力は以下の形式で標準入力から与えられる。

    
     $ T $ 
     $ n_1 $   $ k_1 $ 
     $ n_2 $   $ k_2 $ 
    :
     $ n_T $   $ k_T $ 
    • $ 1 $ 行目には、テストケースの数を表す整数 $ T\ (1≦T≦100000) $ が与えられる。
    • $ 2 $ 行目から $ T $ 行は、高橋君の条件に関する整数 $ n $ , $ k $ が、 $ 1 $ 行ごとに与えられる。 このうち $ i $ 行目には、 $ i $ 番目のテストに対する高橋君の条件 $ n_i,\ k_i\ (0≦k_i≦n_i≦100000) $ が、スペース区切りで与えられる。

    输出格式:

    高橋君の個数を $ 1000000007 $ で割った余りをそれぞれ $ 1 $ 行ずつ、 $ T $ 行で出力せよ。出力の末尾には改行をいれること。

    输入输出样例

    输入样例#1: 复制
    10
    1 1
    3 2
    5 2
    8 3
    12 0
    642 246
    2222 999
    2525 21
    50000 25000
    100000 100000
    输出样例#1: 复制
    2
    7
    16
    93
    1
    321969783
    856998846
    371661809
    969409843
    607723520

    说明

    部分点

    $ 0≦k_i≦n_i≦3000 $ の条件を満たすテストケースに全て正解した場合、 $ 50 $ 点が得られる。

    全てのテストケースに正解した場合、さらに $ 150 $ 点が得られる。

    高橋君の個数を $ 1000000007 $ で割った余りをそれぞれ $ 1 $ 行ずつ、 $ T $ 行で出力せよ。出力の末尾には改行をいれること。

    Sample Explanation 1

    $ n=1 $ , $ k=1 $ の時、高橋君は、0, 1 の $ 2 $ つです。 $ n=3 $ , $ k=2 $ の時、高橋君は、000, 001, 010, 011, 100, 101, 110 の $ 7 $ つです。 大きな数の時には、 $ 1000000007 $ で割った余りを出力することに注意してください。

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