列表

详情


NC23935. 小w的禁忌与小G的长诗

描述

自从上次小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

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 476K, 提交时间: 2019-04-27 21:50:54

#include<iostream>
using namespace std;
typedef long long int ll;
ll mod=1e9+7;
ll fun(ll x,ll y)
{
	ll res=1;
	while(y>0)
	{
		if(y&1)
		{
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res%mod;
}
int main()
{
	ll n,s=0,t,t1,t2;
	cin>>n;
	s=3*fun(25,n)+3*mod-3*fun(24,n)+fun(23,n);
	cout<<s%mod<<endl;
	return 0;
}

C++(clang++11) 解法, 执行用时: 4ms, 内存消耗: 380K, 提交时间: 2020-11-01 14:48:30

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll M=1e9+7,n;
ll k(ll a,ll b)
{
	ll s=1;
	for(;b;b/=2)
	{
		if(b&1)s=s*a%M;
		a=a*a%M;
	}return s;
}int main()
{
    ios::sync_with_stdio(0);
	cin>>n;
	cout<<((k(23,n)-3*k(24,n)+3*k(25,n))%M+M)%M; 
}

Python3(3.5.2) 解法, 执行用时: 27ms, 内存消耗: 3572K, 提交时间: 2019-08-22 10:48:24

n = int(input())
mod = 10**9+7
ans = 3*(pow(25,n,mod)-pow(24,n,mod))+pow(23,n,mod)
print(ans%mod)

上一题