传话游戏
思路
分析题目后不难发现，对于一个单词只可以和前后进行交换。
问题变为：有 \(n\) 个单词只可以前后交换问，每个单词至多交换一次，求最后的单词序列种数。
设 \(f[i][0/1/3]\) 为前 \(i\) 个单词，\(0\)：与前面的单词交换的方案数，\(1\)：不交换的方案数，\(3\)：该单词操作后的种类总数。
由于与后面的单词交换可以看做后面的单词与前面交换，故不考虑。（实际上状态也不允许这么做）
当 \(s[i]==s[i-1]\) 时：
\[f[i][0]=f[i-2][3]\\ f[i][1]=f[i-1][3]\\ f[i][3]=f[i][1] \]当 \(s[i]\neq[i-1]\) 时：
\[f[i][0]=f[i-2][3]\\ f[i][1]=f[i-1][3]\\ f[i][3]=f[i][0]+f[i][1] \]发现方程其实只需要求 \(f[i][3]\)，遂演变为：
当 \(s[i]==s[i-1]\) 时：
\[f[i]=f[i-1] \]当 \(s[i]\neq[i-1]\) 时：
\[f[i]=f[i-1]+f[i-2] \]特别的 \(f[0]=f[1]=1\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
const int maxn=1e5+5;
int n;
int f[maxn];
string s[maxn];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) cin>>s[i];
f[1]=1;
if(s[2]==s[1]) f[2]=1;
else f[2]=2;
for(int i=3;i<=n;i++)
{
if(s[i]==s[i-1]) f[i]=f[i-1];
else f[i]=(f[i-1]+f[i-2])%mod;
}
printf("%lld",f[n]%mod);
}