大意：給你一個整數N，代表字元串長度，每個位置上的字元可以是’C’ 或者 ‘P’，長度為N的字元串中有2^N種，為這些字元串中，包含幾個‘CCPC’（一個字元串中的有貢獻的ccpc要求不重疊）
思路：
長度為N，
包含一個‘CCPC’：
空的位置數是N-4，每個位置可以填兩種字元，由插空法可知‘ccpc’有（N-4 +1）種插法，則共有2^(N-4) *（N-4 +1）種
包含兩個‘CCPC’：
與上同理
共有2^(N-7) *（N-7 +1）種
包含…
但是注意!!!
ccpc . . . .
. . . . ccpc
第一個字元串填成ccpcccpc
第二個字元串填成ccpcccpc時，這是構成了同一種字元串，但是 兩種ccpc的位置不同，是以在算的時候會算重，這就用到了容斥定理
是以總的答案=包含一個‘ccpc’的種數 - 包含兩個個‘ccpc’的種數 + 包含三個‘ccpc’的種數 - 包含四個‘ccpc’的種數 …
例：
當 N=10時
總的答案=（6 +1）* 2 ^ 6 - （3 +1）* 2 ^ 3 + （0+1）* 2 ^ 0
我們把相加的項放一起，相減的項放一起，分開算
ans = （6 +1）* 2 ^ 6 + （0+1）* 2 ^ 0 （最小空位數是0，有兩項）
ans2 = （3 +1）* 2 ^ 3 （最小空位數是3，有一項）
答案= ans - ans2
最終式子的化簡如下（錯位相減法）：
（N=10，ans的m=0，n=2 ， ans2的m=3，n=1）
代碼實作時别忘了取模+逆元
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#pragma warning(disable:4996)
#define inr register int
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int maxn = 200007;//1e5+7
const ll mod = 1000000007;//1e9+7
ll ksm(ll x, ll y)
{
ll ans = 1;
x = x % mod;
while (y > 0)
{
if (y & 1) ans = (ans * x) % mod;
y >>= 1;
x = (x * x) % mod;
}
return ans%mod;
}
ll inv(ll x)
{
return ksm(x, mod - 2);
}
int main()
{
ios;
int T;
ll n;
cin >> T;
while (T--)
{
cin >> n;
if(n<4)cout<<0<<endl;
else
{
ll m = (n - 4ll) % 6;
ll N = (n - 4ll) / 6+1;
// cout<<N<<" "<<m<<endl;
ll ans = (((m + 1)%mod * ksm(2, m) % mod)%mod + (6ll * ksm(2, m + 6) % mod * (ksm(2, 6ll*N-6) - 1 + mod) % mod * inv(63) % mod)%mod-(((m+6ll*N-5))%mod*ksm(2,m+6*N)%mod)%mod+mod) % mod;
ll fm = (-63 + mod) % mod;
fm = inv(fm);
ans = ans * fm % mod;
// cout<<ans<<endl;
ll ans2=0;
if(n>=7)
{
m = (n - 7ll) % 6;
N = (n - 7ll) / 6+1;
ans2 = (((m + 1)%mod * ksm(2, m) % mod)%mod + (6ll * ksm(2, m + 6) % mod * (ksm(2, 6ll*N-6) - 1 + mod) % mod * inv(63) % mod)%mod-(((m+6ll*N-5))%mod*ksm(2,m+6*N)%mod)%mod+mod) % mod;
fm = (-63 + mod) % mod;
fm = inv(fm);
ans2 = ans2 * fm % mod;
}
cout << (ans - ans2 + mod) % mod << endl;
}
}
return 0;
}