本文主要是介绍P2012 拯救世界2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
前三题太弱了嘛，在看看最后一道渣题。
题目描述
经过 12 年的韬光养晦，世界末日再次来临（众人：什么鬼逻辑......）。
这次，小a 和 uim 已经做好了一切准备，顺利召唤出了 kkksc03 大神和 lzn 大神。然而，kkksc03 和 lzn 告诉他们，这次世界末日太过强大，他们已无法挽回，只有创世神 JOHNKRAM 能拯救这个世界。
然而，创世神 JOHNKRAM 是无法召唤的，除非把整个宇宙按照 𝐸=𝑚𝑐2E=mc2 全部转化成能量。因为根据 C_SUNSHINE 大神随手推算出的召唤定律，至少需要被召唤者百万亿分之一的能量才能召唤（众人：什么鬼定律......）。
当然，还有一种方法，那就是找出创世神 JOHNKRAM 的基因序列。普通人基因序列由 A、C、G、T 构成，创世神 JOHNKRAM 不是普通人（是个胖纸），基因序列也不一样。除了这四种普通的，还有乾、兑、离、震、巽、坎、艮、坤八种特殊基因。其中乾、坎、艮、震属阳，只能出现奇数次；坤、兑、离、巽属阴，只能出现偶数次。
现在只知道创世神 JOHNKRAM 的基因序列共有 𝑛n 位，其他一概不知。小a 和 uim 想知道他们最多要试多少次，才能召唤出创世神 JOHNKRAM 。这个数字有可能很大，所以输出答案模 109109 即可（C_SUNSHINE 的忠告：远离八卦，远离肥胖）。
输入格式
输入由多组数据组成，每组数据一行，输入一个数 𝑛n，输入以 00 结束。
输出格式
对于每组数据，输出一行一个整数，表示答案对 109109 取模的结果。
输入输出样例
输入 #1
3 10 20 6 0
输出 #1
0 225116160 53238784 7680
说明/提示
【数据范围】
对于 10%10% 的数据：1≤𝑛<251≤n<25，数据不超过 1010 组；
对于 50%50% 的数据：1≤𝑛<2311≤n<231，数据不超过 103103 组；
对于 100%100% 的数据：1≤𝑛<2631≤n<263，数据不超过 2×1052×105 组。
【样例解释】
第一个数据解释：
只有 33 位，没有合法方案，故答案为 00。
【备注】
附件：聊天记录（纯粹扯淡）
JOHNKRAM 8:50:33
喂喂，坑神之赛2可以开始了吧
C_SUNSHINE 8:50:34
[自动回复]恩！
JOHNKRAM 8:51:12
我准备把最后一题数据从 5050 放到 263263。
C_SUNSHINE 8:51:12
[自动回复]恩！
JOHNKRAM 8:51:45
你同意喽？
C_SUNSHINE 8:51:46
[自动回复]恩！
C_SUNSHINE 11:58:50
你疯了吗？！
JOHNKRAM 11:58:52
[自动回复]您好，我现在有事不在，一会再和您联系。 不再提醒
Code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
const ll b[5]={0,0,0,0,24},T=20000,N=T+10,P=1e9,Phi=4e8;
ll n,pw2[N],pw3[N],Pw2[N],Pw3[N];
ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c))x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f;
}
void print(ll x)
{if(x>9)print(x/10);putchar(x%10+48);return;}
ll G4(ll n)
{n%=Phi;return Pw2[n/T]*Pw2[n/T]%P*pw2[n%T]%P*pw2[n%T]%P;}
ll G8(ll n)
{n%=Phi;return Pw2[n/T]*pw2[n%T]%P*G4(n)%P;}
ll G12(ll n)
{n%=Phi;return Pw3[n/T]*pw3[n%T]%P*G4(n)%P;}
signed main()
{pw2[0]=pw3[0]=Pw2[0]=Pw3[0]=1;for(ll i=1;i<=T;i++)pw2[i]=pw2[i-1]*2ll%P,pw3[i]=pw3[i-1]*3ll%P;for(ll i=1;i<T;i++)Pw2[i]=Pw2[i-1]*pw2[T]%P,Pw3[i]=Pw3[i-1]*pw3[T]%P;while(1){n=read();if(!n)break;if(n<=4){print(b[n]),putchar('\n');continue;}ll ans=81ll*G12(n-4);ans=ans-G8(n-2);ans=ans+6ll*G4(n-4);ans=ans+((n&1)?-1:1)*G4(n-4);print((ans%P+P)%P);putchar('\n'); }return 0;
}
这篇关于P2012 拯救世界2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
