#P3178. [Coci2012]funkcija

    ID: 2354 传统题 1000ms 512MiB 尝试: 80 已通过: 36 难度: 6 上传者: 标签>难度分类普及+/提高-动态规划树形 DP前缀和优化 DP组合数学乘法原理CF1900

[Coci2012]funkcija

[COCI 2011/2012 #2] FUNKCIJA

题目描述

Mirko 写了一个含 NN 层循环的函数。它按字母顺序给各层循环的变量命名,从 a 开始。第 ii 层循环将变量从 XiX_i 递增到 YiY_i,包括两端。每次进入最内层循环体,计数器加一并对 109+710^9+7 取模。计数器初值为零。

C++ 伪代码:

int fun() {
    int ret = 0;
    for (int a = X1; a <= Y1; ++a)
        for (int b = X2; b <= Y2; ++b)
            ...
                for (int <N-th> = XN; <N-th> <= YN; ++<N-th>)
                    ret = (ret + 1) % 1000000007;
    return ret;
}

Pascal 伪代码:

function fun: longint;
var
  ret: longint;
  a, b, ... , y, z: longint;
begin
  ret := 0;
  for a := X1 to Y1 do
    for b := X2 to Y2 do
      ...
        for <N-th> := XN to YN do
          ret := (ret + 1) mod 1000000007;
  fun := ret;
end;

<N-th> 表示第 NN 个英文小写字母。每个 Xi,YiX_i,Y_i 可以是 11 到 10510^5 的整数常量,也可以是某个外层循环的变量名,例如 X3X_3 可以是 a、b 或整数常量。对每个 ii,Xi,YiX_i,Y_i 至少有一个是整数常量。若某次循环的下界大于上界,这次循环体执行零次。

求函数的返回值。

输入格式

第一行包含一个整数 NN(1≤N≤261\le N\le 26)。

接下来 NN 行,第 ii 行包含用空格分隔的 Xi,YiX_i,Y_i。两者均为整数常量时,保证 Xi≤YiX_i\le Y_i。

输出格式

输出一行一个整数,表示函数的返回值。

2
1 2
a 3
5
3
2 3
1 2
1 a
10
3
1 2
a 3
1 b
11

原题面 PDF