# 2272: [Usaco2011 Feb]Cowlphabet 奶牛文字

## 2272: [Usaco2011 Feb]Cowlphabet 奶牛文字

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 138  Solved: 97

[Submit][Status][Discuss]

## Description

Like all bovines, Farmer John's cows speak the peculiar 'Cow' language. Like so many languages, each word in this language comprises a sequence of upper and lowercase letters (A-Z and a-z).  A word is valid if and only if each ordered pair of adjacent letters in the word is a valid pair. Farmer John, ever worried that his cows are plotting against him, recently tried to eavesdrop on their conversation. He overheard one word before the cows noticed his presence. The Cow language is spoken so quickly, and its sounds are so strange, that all that Farmer John was able to perceive was the total number of uppercase letters, U (1 <= U <= 250) and the total number of lowercase letters, L (1 <= L <= 250) in the word. Farmer John knows all P (1 <= P <= 200) valid ordered pairs of adjacent letters.  He wishes to know how many different valid words are consistent with his limited data.  However, since this number may be very large, he only needs the value modulo 97654321.

约翰的奶牛讲的是别人听不懂的“牛语”。牛语使用的字母就是英文字母，有大小写之分。牛语中存在P个合法的词素，每个词素都由两个字母组成。牛语的单词是由字母组成的序列，一个单词是有意义的充要条件是任意相邻的字母都是合法的词素。

约翰担心他的奶牛正在密谋反对他，于是最近一直在偷听他们的对话。可是，牛语太复

## Input

* Line 1: Three space-separated integers: U, L and P * Lines 2..P+1: Two letters (each of which may be uppercase or         lowercase), representing one valid ordered pair of adjacent         letters in Cow.

第一行：三个用空格隔开的整数：U，L和P，1≤U．L≤250，1≤P<=200

第二行到P+1行：第i+l有两个字母，表示第i个词素，没有两个词素是完全相同的

## Output

* Line 1: A single integer, the number of valid words consistent with         Farmer  John's data mod 97654321. 单个整数，表示符合条件的单词数量除以97654321的余数

## Sample Input

2 2 7 AB ab BA ba Aa Bb bB INPUT DETAILS: The word Farmer John overheard had 2 uppercase and 2 lowercase letters. The valid pairs of adjacent letters are AB, ab, BA, ba, Aa, Bb and bB.

7

## HINT

(可能的单词为AabB, Abba, abBA, BAab,BbBb, bBAa, bBbB)

## Source

Gold

（PS：我在想如果出数据的人比较良心的话，万一弄一大堆数据L=0的该怎么办QAQ，更可怕的是万一再弄一大堆U=0的。。。那样子的话如果再加强U、L的话，就能轻松让大部分程序TLE了呵呵，不过这道题里面就算是O(52(U+L)^2)也完全能过，不怕）

``` 1 const q=97654321;
2 type
3     point=^node;
4     node=record
5                g:longint;
6                next:point;
7     end;
8 var
9    i,j,k,l,m,n:longint;
10    b:array[0..300,1..2] of longint;
11    c:array[0..600,0..300,0..60] of longint;
12    a:array[0..60] of point;
13    c1,c2:char;p:point;
14 function callback(ch:char):longint;inline;
15          begin
16               if ch>='a' then exit(ord(ch)-ord('a')+1) else exit(ord(ch)-ord('A')+27);
17          end;
19           var p:point;
20           begin
21                new(p);p^.g:=y;
22                p^.next:=a[x];a[x]:=p;
23           end;
24 function min(x,y:longint):longint;inline;
25          begin
26               if x<y then min:=x else min:=y;
27          end;
28
29 begin
31      for i:=1 to 52 do a[i]:=nil;
32      fillchar(c,sizeof(c),0);
33      for i:=1 to l do
34           begin
36                b[i,1]:=callback(c1);
37                b[i,2]:=callback(c2);
39                if b[i,1]>26 then c[1,1,b[i,1]]:=1 else c[1,0,b[i,1]]:=1;
40           end;
41      for i:=2 to n+m do
42          for j:=0 to min(n,i) do
43              for k:=1 to 52 do
44                  begin
45                       p:=a[k];
46                       while p<>nil do
47                             begin
48                                  if k>26 then
49                                     begin
50                                          if j>0 then c[i,j,k]:=(c[i,j,k]+c[i-1,j-1,p^.g]) mod q;
51                                     end
52                                  else
53                                      c[i,j,k]:=(c[i,j,k]+c[i-1,j,p^.g]) mod q;
54                                  p:=p^.next;
55                             end;
56                  end;
57      l:=0;
58      for i:=1 to 52 do l:=(l+c[n+m,n,i]) mod q;
59      writeln(l);
60 end.     ```

250 篇文章37 人订阅

0 条评论

## 相关文章

### 1741: [Usaco2005 nov]Asteroids 穿越小行星群

1741: [Usaco2005 nov]Asteroids 穿越小行星群 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

2726

### 2015: [Usaco2010 Feb]Chocolate Giving

2015: [Usaco2010 Feb]Chocolate Giving Time Limit: 10 Sec  Memory Limit: 162 MB S...

3086

### 1634: [Usaco2007 Jan]Protecting the Flowers 护花

1634: [Usaco2007 Jan]Protecting the Flowers 护花 Time Limit: 5 Sec  Memory Limit:...

3248

### 1753: [Usaco2005 qua]Who's in the Middle

1753: [Usaco2005 qua]Who's in the Middle Time Limit: 5 Sec  Memory Limit: 64 MB ...

33111

### 1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

1734: [Usaco2005 feb]Aggressive cows 愤怒的牛 Time Limit: 5 Sec  Memory Limit: 64 MB...

2787

### 1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课 Time Limit: 5 Sec  Memory Limit: 64 M...

2846

### 3314: [Usaco2013 Nov]Crowded Cows

3314: [Usaco2013 Nov]Crowded Cows Time Limit: 1 Sec  Memory Limit: 128 MB Submit...

2615

### 1635: [Usaco2007 Jan]Tallest Cow 最高的牛

1635: [Usaco2007 Jan]Tallest Cow 最高的牛 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

3235

### 1671: [Usaco2005 Dec]Knights of Ni 骑士

1671: [Usaco2005 Dec]Knights of Ni 骑士 Time Limit: 5 Sec  Memory Limit: 64 MB Su...

2635

### 1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

2997