题干：

链接：https://ac.nowcoder.com/acm/contest/696/C
来源：牛客网
 

自从上次小w被奶牛踹了之后，就一直对此耿耿于怀。

于是"cow"成为了小w的禁忌，而长得和"cow"很像的"owc"…凡是同时含有"c","w","o"的都进入了他的禁忌名单。

小G想给他送一幅幅长为n个字符的长诗，但是又怕触犯他的禁忌。所以他决定要是诗中出现了他的禁忌就宁可不送，可是...他一写起诗来就忘了一切。

小G想知道他有多少种的诗可能不触犯他的禁忌

注：小G只会用小写字母写诗

输入描述:

一行一个整数n表示诗的长度

输出描述:

一行一个整数表示小G有多少种可能的诗不触犯小W的禁忌，由于可能数也许过大，请对109+7取膜后输出

示例1

输入

3

输出

17570

说明

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

备注:


 

对于30%30%的数据满足1≤n≤51≤n≤5

对于100%100%的数据满足1≤n≤105

解题报告：

dp的思路不难想 ，就是dp[i][j] 前i个字符出现了 j 种 禁忌字符，注意是种，所以递推方程就不难推了。复杂度On。

这题还有logn的做法，直接考虑容斥：答案=C(3,2)*可能含有两个非法字符的方案数-C(3,1)*可能含有一个非法字符的方案数+C(3,0)*不含非法字符的方案数=C(3,2)*pow(25,n) - C(3,1)*pow(24,n) + C(3,0)*pow(23,n);直接快速幂求解，复杂度logn。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
const ll mod = 1e9+7;
ll dp[MAX][3];
int n;
int main()
{
	cin>>n;
	dp[1][0]=23;dp[1][1]=3;dp[1][2]=0;
	for(int i = 2; i<=n; i++) {
		dp[i][0] = (dp[i-1][0] * 23)%mod;
		dp[i][1] = (dp[i-1][0] * 3 + dp[i-1][1]*24)%mod;
		dp[i][2] = (dp[i-1][1] * 2 + dp[i-1][2]*25)%mod;
	}
	printf("%lld\n",(dp[n][0]+dp[n][1]+dp[n][2])%mod);
	return 0 ;
}