牛客——小w的禁忌與小G的長詩（容斥原理）

小w的禁忌與小G的長詩

題目描述

自從上次小w被奶牛踹了之后，就一直對此耿耿于懷，
于是"cow"成為了小w的禁忌，而長得和"cow"很像的"owc"…凡是同時含有"c",“w”,"o"的都進入了他的禁忌名單，
小G想給他送一幅幅長為n個字符的長詩，但是又怕觸犯他的禁忌，所以他決定要是詩中出現了他的禁忌就寧可不送，可是…他一寫起詩來就忘了一切，
小G想知道他有多少種的詩可能不觸犯他的禁忌
注：小G只會用小寫字母寫詩

輸入描述:

一行一個整數n表示詩的長度

輸出描述:

一行一個整數表示小G有多少種可能的詩不觸犯小W的禁忌，由于可能數也許過大，請對 1 0 9 + 7 10^9+7 109+7取膜后輸出

輸入

3

輸出

17570

說明

n=3且包含"c",“o”,"w"的只有6個串，所以答案是26^3-6=17570

備注:

對于 30 % 30\% 30%的資料滿足 1 ≤ n ≤ 5 1\leq n\leq 5 1≤n≤5
對于 100 % 100\% 100%的資料滿足 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105

解決思路：容斥原理

提示：簡記容斥原理：奇加偶減，
已知：需要求解的是不含"c",“o”,"w"的字串的數量，
計算貢獻：將題目要求換一種表述方式，
求解的個數：不含"c"或者不含"o"或者不含"w"的字串的數量，
咦！這不就是容斥原理等式的左邊嗎？
So
不含"c"或者不含"o"或者不含"w"的數量 = = = 不含"c"的數量 + + + 不含"o"的數量 + + + 不含"w"的數量 ? - ? 不含"c"并且不含"o"的數量 ? - ? 不含"o"并且不含"w"的數量 ? - ? 不含"c"并且不含"w"的數量 + + + 不含"c"并且不含"o"并且不含"w"的數量，
由于不含一個字母的個數都相同，不含兩個字母的個數也相同，
所以等式變為：
不含"c"或者不含"o"或者不含"w"的數量 = = = 3 × \times ×不含"c"的數量 ? - ? 3 × \times ×不含"c"并且不含"o"的數量 + + + 不含"c"并且不含"o"并且不含"w"的數量，

代碼

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define mod 1000000007
typedef long long ll;
const int N = 1e5 + 10;

ll qpow(ll a, ll b, ll p) {
	ll res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}
	return res;
}


int main() {

	int n; cin >> n;

	ll ans = 3LL * qpow(25, n, mod) % mod - 3 * qpow(24, n, mod) % mod + qpow(23, n, mod);
	ans = (ans % mod + mod) % mod;
	cout << ans << endl;
	return 0;
}