dp，斐波那契数列

题意：

分析：

我们现列举简单的例子：

对第一个例子，he he zhou is watching you
我们简写为： a a b c d e
那么一共有几种呢？
首先自己是一个
然后我们两两交换：
a (b a) c d e a a (c b) d e a a b (d c) e a a b c (d e)
一共四种
尝试交换更多：
a (b a) (d c) e a (b a) c (d e) a a (c b) (e d)
一共三种。
总共八种！

我们看上式似乎发现了什么，对开头的a a明显其中一个是多余的。
那么我们不妨先考虑 a b c d e 即相邻单词都不相同的情况。
这时候我们怎么求呢?
分为两种情况：
1.我们交换前两个元素(b a)那么求的就是 c d e 长度为3的情况的种类
2.我们前两个不交换 那么求的就是 b c d e 长度为4的情况下的种类
如此我们的dp就出来了：
dp[i]表示长度为i的两两不相同的字符串情况种类
动态转移方程：
dp[i] = dp[i-1]+dp[i-2]
有没有发现很眼熟？斐波那契数列！
正好dp[1] = 1,dp[2] = 2

如此我们对于任意字符串假如：
a b c d d d e f g
我们求 a b c d的情况种类dp[4]
求 d e f g 的情况种类dp[4]

答案为：dp[4]*dp[4]
即以出现重复元素为分界点，计算两边的情况再相乘！！

代码如下：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
const int max_n = 1e5 + 100;
const int mod = 1e9 + 7;
typedef pair<string, int> psi;
psi ward[max_n];
int d[max_n];
int n;

int main() {
    ios::sync_with_stdio(0);
    d[1] = 1;d[2] = 2;
    for (int i = 3;i <= 1e5;i++)
        d[i] = (d[i - 1] + d[i - 2]) % mod;
    int T;cin >> T;
    while (T--) {
        cin >> n;
        ll ans = 1;
        string s1, s2;
        int i = 1;int j;
        for (j = 1;j <= n;j++) {
            cin >> s2;
            if (s2 == s1) {
                ans = ((ans % mod) * (d[j - i] % mod)) % mod;
                i = j;
            }s1 = s2;
        }
        if (i != j - 1) {
            ans = ((ans % mod) * (d[j - i] % mod)) % mod;
        }
        cout << ans << endl;
    }
}