E - CCPC Strings HDU - 6942 数列求和+逆元+容斥

E - CCPC Strings HDU - 6942 数列求和+逆元+容斥
E - CCPC Strings HDU - 6942 数列求和+逆元+容斥
大意:给你一个整数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)
E - CCPC Strings HDU - 6942 数列求和+逆元+容斥
代码实现时别忘了取模+逆元

#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;
}



上一篇:【题解】Luogu-P4774 [NOI2018] 屠龙勇士


下一篇:P4774 [NOI2018]屠龙勇士(exCRT,multiset)