刷漆

DP

题面

你的花园里有一个由$N$块排成一条直线的木板组成的栅栏,木板从左到右依次标号 $1$到$N$。

这$N$块木板中,有$M$块木板前面放着一桶油漆。油漆有不同的颜色,每种颜色可以由一个大写字母表示($A$到$Z$)。而你要求$Czy$用他的油漆刷子给栅栏刷上油漆。

已知 Czy 会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后,他开始随机地沿着栅栏走,他不会走出栅栏的范围。随机地走表示$Czy$会沿着他选择的方向一直走,然后随机在任何时候改变方向。沿着栅栏走只有两个方向,向前和向后。
你发现$Czy$刷油漆的过程总是符合下列规则:

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

已知木板可以被多次刷上油漆,每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候,$Czy$才能停下来(当然他也可以继续刷到他想停下来为止)。

你看着$Czy$在栅栏前来回舞动,突然想知道$Czy$停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时,两种油漆方案被视为是不同的。

解析

完美诠释了越长的题目越简单
首先头尾连续的无油漆桶段不影响答案，去掉不考虑。
然后对于任意两个连续的油漆桶中的段落（假设坐标分别为$a$,$b$）可以有$b-a$种油漆方案，则所有段落的方案数乘积即为所求。
注意不算两个相同颜色油漆桶之间的情况。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=1e9+9;
ll n,m;
struct node{int a;char b;bool operator < (const node &o) const{ return a<o.a;}}p[500005];
ll ans=1,las,now;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
int main()
{
  freopen("paint.in","r",stdin);
  freopen("paint.out","w",stdout);
  n=gi();m=gi();
  fp(i,1,m)
    {
      char gun;cin>>p[i].b;
      p[i].a=gi();
    }
  sort(p+1,p+1+m);
  fp(i,2,m) {if(p[i].b!=p[i-1].b) (ans*=(p[i].a-p[i-1].a))%=mod;}
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}