题解 P6103 【直接自然溢出啥事没有】
引领天下
2020-02-15 18:23:47
这个题是真的善良……标题提示取模方式(
经过探索,我们发现这个对 $2^{64} $ 取模真的就是自然溢出,啥事没有。
考虑按题意模拟,但是需要注意更新顺序。
具体看代码:
```cpp
#include <bits/stdc++.h>
#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))
using namespace std;
unsigned long long a[10001]={1}/*程序片段*/,b[10001]={0,1}/*语句*/,c[10001]/*语句块*/,d[10001]/*函数*/,e[10001]/*值*/;
int n;
inline void write(unsigned long long n){
if(!n)return ;
write(n/10);
putchar(n%10+'0');
}
int main(){
scanf("%d",&n);
for (int i=0;i<=n;i++){
if(i+2<=n)d[i+2]+=d[i];//A为函数,(A)为函数
if(i+2<=n)e[i+2]+=e[i];e[i]+=d[i];if(i+2<=n)e[i+2]+=d[i];//A为函数,A是值,A()是值
//↑注意坑点↑!一定要在更新e[i]之前更新e[i+2],否则e[i+2]中d[i]将会被加两次!
if(i+1<=n)b[i+1]+=e[i];//A是值,(A)是值,A;是语句
b[i]+=c[i];if(i+2<=n)d[i+2]+=c[i];if(i+4<=n)d[i+4]+=c[i];//A是语句块,A是语句,[]A是函数,[]()A是函数
for(int j=0;j<i;j++)a[i]+=a[j]*b[i-j];//A是程序片段,B是语句,AB是程序片段
if(i+2<=n)c[i+2]+=a[i];//{A}是语句块
}
if(a[n])write(a[n]);
else putchar('0');
return 0;
}
```