刷漆（Codechef October Challenge 2014：Remy paints the fence）

【问题描述】

Czy做完了所有的回答出了所有的询问，结果是，他因为脑力消耗过大而变得更虚了:)。帮助Czy恢复身材的艰巨任务落到了你的肩上。

正巧，你的花园里有一个由N块排成一条直线的木板组成的栅栏，木板从左到右依次标号1到N。这N块木板中，有M块木板前面放着一桶油漆。油漆有不同的颜色，每种颜色可以由一个大写字母表示(A到Z)。而你要求Czy用他的油漆刷子给栅栏刷上油漆。

已知Czy会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后，他开始随机地沿着栅栏走，他不会走出栅栏的范围。随机地走表示Czy会沿着他选择的方向一直走，然后随机在任何时候改变方向。沿着栅栏走只有两个方向，向前和向后。

你发现Czy刷油漆的过程总是符合下列规则:

• 每个油漆桶里装着无限多的油漆；
• 刷子上每次只有一种颜色的油漆，每次蘸油漆都会完全替换刷子上的油漆颜色；
• 当Czy走到一个油漆桶前，他会首先用刷子蘸这个油漆桶里的油漆；
• Czy每走过一个木板都会将这个木板刷成当前刷子上的油漆颜色。

已知木板可以被多次刷上油漆，每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候，Czy才能停下来(当然他也可以继续刷到他想停下来为止)。你看着Czy在栅栏前来回舞动，突然想知道Czy停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时，两种油漆方案被视为是不同的。

请你输出不同的油漆方案数对10⁹+9取模的值。

 

【输入】

输入文件为 paint.in。

输入的第一行包含两个整数N和M。

接下来M行，每行两个整数x和y，表示第y块木板前面有一个装着颜色为x的油漆的油漆桶。

 

【输出】

输出文件为 paint.out。

输出一行，包含一个整数，表示不同的油漆方案数对109 + 9取模的结果。

 

【输入输出样例】

 

paint.in	paint.out
6 2 A 2 B 6	4

 

【数据范围】

对于30% 的数据，1 ≤ M ≤ N ≤ 100。

对于100% 的数据， 1 ≤ M ≤ N ≤ 100000。

x是A到Z之间的大写字母；1 ≤ y ≤ N。

【解题思路】

很容易得到，从头到第一个油漆桶的颜色和最后一个油漆桶到结束的颜色只有一种，不予考虑。对于任意两个油漆桶之间的栅栏分析（如果这两种油漆不同），共有N块栅栏，如果有a块栅栏选1颜色，那另外（n-a）块就是b颜色（这些块必须连续），这样统计下来共有（n+1）种方案，累乘之后就可以得出答案。

【Tip】

数据比较大，需要开int64（long long）

需要先排一边序(样例坑)

program paint;
type aa=record
ch:char;
x:longint;
end;
const mo=1000000009;
procedure open;
begin
    assign(input,'paint.in');
    assign(output,'paint.out');
    reset(input);
    rewrite(output);
end;

procedure closs;
begin
    close(input);
    close(output);
end;

var a:array[0..100000] of aa;
    n,m,i,mid:longint;
    ans:int64;
procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].x;
         repeat
           while a[i].x<x do
            inc(i);
           while x<a[j].x do
            dec(j);
           if not(i>j) then
             begin
                a[0]:=a[i];
                a[i]:=a[j];
                a[j]:=a[0];
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

begin
    open;
    readln(n,m);
    for i:=1 to m do
    begin
        readln(a[i].ch,a[i].x);
    end;
    sort(1,m);
    ans:=1;
    for i:=1 to m-1 do
    begin
        if a[i].ch=a[i+1].ch then continue;
        mid:=a[i+1].x-a[i].x;

        ans:=(ans*mid) mod mo;
    end;
    if ans=0 then ans:=1;
    writeln(ans);
    closs;
end.