题意：

 给你一个有n个单词的单词串S，对这n个单词进行排列组合形成新的一个单词串T，如果在S中任意某个单词所在位置，和这个单词在T中所在位置之差的绝对值小于等于1，那么就说S和T串相等

让你求S一共有多少与之相等的串

 

题解：

刚开始以为规律就是斐波那契，交了一发wa了

 

首先如果n==1时，dp[1]=0

用f[i]表示S串的第i个单词，则如果对于n+1的S串，如果f[n]==f[n+1]，那么dp[n]==dp[n+1]

如果对于n+1的S串，如果f[n]!=f[n+1]，那么dp[n+1]=dp[n]+dp[n-1]，其中dp[n]就相当于在之前的dp[n]种类型的T串后面加了一个单词f[n+1]，加上dp[n-1]，是因为如果f[n]和f[n+1]单词交换，那么又多了dp[n-1]种

 

代码：

#include <stack>
#include <queue>
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
const ll mod = 1000000007;
ll fac[maxn];
ll inv[maxn];
ll n;
string a[maxn];
ll dp[maxn];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        ll ans = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++)
        {
            if (a[i] == a[i - 1])
                dp[i] = dp[i - 1];
            else
                dp[i] = (dp[i - 1] + dp[i - 2] + 1) % mod;
        }
        printf("%lld\n", dp[n] + 1);
    }
    return 0;
}