hdu 6806 Equal Sentences 找规律
题意：
给你一个有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 ", dp[n] + 1); } return 0; }