NC23935. 小w的禁忌与小G的长诗
描述
自从上次小w被奶牛踹了之后,就一直对此耿耿于怀。
于是"cow"成为了小w的禁忌,而长得和"cow"很像的"owc"…凡是同时含有"c","w","o"的都进入了他的禁忌名单。
小G想给他送一幅幅长为n个字符的长诗,但是又怕触犯他的禁忌。所以他决定要是诗中出现了他的禁忌就宁可不送,可是...他一写起诗来就忘了一切。
输入描述
一行一个整数n表示诗的长度
输出描述
一行一个整数表示小G有多少种可能的诗不触犯小W的禁忌,由于可能数也许过大,请对109+7取膜后输出
示例1
输入:
3
输出:
17570
说明:
n=3且包含"c","o","w"的只有6个串,所以答案是26^3-6=17570C++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)