CF1105C Ayoub and Lost Array

    • 116通过
    • 154提交
  • 题目来源 CodeForces 1105C
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    已知有一个长度为$n$($1\leq n\leq 2 \times 10^5$)的数列,每一个数的大小在$[l,r]$($1\leq l \leq r \leq 10^9$)之间。求出有多少种方案使得这个数列的和为$3$的倍数。答案对$10^9+7$取模。当然,如果无法组成任何一个合法的数列,答案即为$0$。

    输入格式

    一行三个正整数$n$,$l$,$r$

    输出格式

    一行,表示方案数模$10^9+7$的结果。

    题目描述

    Ayoub had an array $ a $ of integers of size $ n $ and this array had two interesting properties:

    • All the integers in the array were between $ l $ and $ r $ (inclusive).
    • The sum of all the elements was divisible by $ 3 $ .

    Unfortunately, Ayoub has lost his array, but he remembers the size of the array $ n $ and the numbers $ l $ and $ r $ , so he asked you to find the number of ways to restore the array.

    Since the answer could be very large, print it modulo $ 10^9 + 7 $ (i.e. the remainder when dividing by $ 10^9 + 7 $ ). In case there are no satisfying arrays (Ayoub has a wrong memory), print $ 0 $ .

    输入输出格式

    输入格式:

    The first and only line contains three integers $ n $ , $ l $ and $ r $ ( $ 1 \le n \le 2 \cdot 10^5 , 1 \le l \le r \le 10^9 $ ) — the size of the lost array and the range of numbers in the array.

    输出格式:

    Print the remainder when dividing by $ 10^9 + 7 $ the number of ways to restore the array.

    输入输出样例

    输入样例#1: 复制
    2 1 3
    
    输出样例#1: 复制
    3
    
    输入样例#2: 复制
    3 2 2
    
    输出样例#2: 复制
    1
    
    输入样例#3: 复制
    9 9 99
    
    输出样例#3: 复制
    711426616
    

    说明

    In the first example, the possible arrays are : $ [1,2], [2,1], [3, 3] $ .

    In the second example, the only possible array is $ [2, 2, 2] $ .

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