描述 Description
Our chef Remy ate all the delicious food he made. As a result, he has become really fat :). Chef’s assistant Linguini has taken up the herculean task of bringing back chef Remy to shape.
Linguini has built a fence which has N planks in a straight line. The planks are numbered 1 to N from left to right. In front of M of these N planks, he has put a bucket of paint. The paints may be of different colors. Each color is represented by any uppercase letter (A-Z). Chef Remy needs to paint the fence. He uses his painting brush to paint the fence.
Chef Remy starts the task by choosing a plank which has a bucket of paint in front of it and dips his brush in the bucket. He starts walking randomly along the straight fence passing the planks. He never moves out of the fence. Note that walking randomly along a fence means that Remy keeps walking all the time along his current direction. He can change his direction any time he wishes. Moving along a straight fence has just two directions, forward and backward.
Linguini has devised the following recipe for painting the fence. Each bucket has an infinite supply of paint.
The brush can carry paint of a single color at any time.
When Remy passes a paint bucket, the brush acquires the color in the bucket first.
Every plank that Remy passes in his random walk must be colored with the color in the brush. A plank will be colored completely.
A plank can be colored multiple times. A plank’s color is the latest color it is painted with.
A fence coloring is complete when each plank is painted with some color. Linguini is watching Remy dance around with colors. He wonders how many different complete fence colorings will he be able to see. Two fence colorings are different if there is atleast one plank numbered x whose color differs in both the colorings. Find out the number of different complete fence colorings modulo 1000000009.
输入格式 InputFormat
First line contains T, the number of test cases. T test cases follow. The first line of each case contains N and M separated by a space. Next M lines follow each of the form x and y separated by a space. Here x is the color in the bucket which is placed at plank numbered y.
输出格式 OutputFormat
The number of different complete fence colorings modulo 1000000009 for each case on a new line.
样例输入 SampleInput
3
2 1
R 1
3 1
A 2
6 2
A 2
B 6
样例输出 SampleOutput
1
1
4
首先头尾连续的无油漆桶段不影响答案，去掉不考虑。然后对于任意两个连续的油漆桶中的段落（假设坐标分别为 a,b）可以有 b-a 种油漆方案，则所有段落的方案数乘积即为所求。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define pr pair<int,char>
const int mod=1000000009;
int i,j,t,n,m,l,r,k,z,y,x;
vector <pr> v;
int T;
char ch[1];
long long ans;
int main()
{
scanf("%d",&T);
while (T--)
{
v.clear();
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) scanf("%s%d",ch,&x),v.push_back(make_pair(x,ch[0]));
sort(v.begin(),v.end());
ans=1;
for (l=r=0;r<v.size();l=r)
{
while (r<v.size() && v[r].second==v[l].second) r++,l=r-1;
if (r==v.size()) break;
ans=(ans*(v[r].first-v[l].first))%mod;
}
printf("%lld\n",ans);
}
return 0;
}