刷题记录:牛客NC205036答题卡

传送门:牛客

牛牛即将要参加考试，他学会了填答题卡。
可惜他竖着的答题卡填成了横着的 : (
好奇的他想知道对于 n 道题，每道题 n 个选项的答题卡 ( n * n 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。
注：每道题只能选择一个选项，即 n * n 的矩阵中只能涂黑 n 个空。求横竖对称的方案数。
输入:
3
输出:
4
1
2
3
4
5
6
7
8

主要思路:
emmm,感觉这道题的递推关系还是比较巧妙的,第一眼我完全被哄住了,感觉这道题挺难啊,这种模拟肯定不行了,n十分的大,枚举必挂,应该有什么规律.然后

1. 刚开始我看了一看n=1时显然是1,n=2时显然是2,n=3时又是4,我焯,当时我一看就兴奋了,然后收画了一下n=4的情况,好像就是8诶(在手画的过程中我似乎感觉到了一点点和前面的关联关系,但是当时也没有总结),然后我感觉答案应该就是2^(n-1),然后敲了一个快速幂,交了一波,很好,得了0分
2. 然后就感觉比较自闭了,果然推算关系是没有这么简单的,静下心来思考了一下,心中感觉一下,确实有规律
   
   然后我们就可以快乐的得到递推公式了,最后注意取模和longlong的细节即可

dp[i]=dp[i-1]+dp[i-2]*(i-1)
1

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int f[100];
int main() {
	int T;T=read();
	f[1]=1;f[2]=2;
	for(int i=3;i<=100;i++) f[i]=f[i-1]+f[i-2];
	while(T--) {
		int a;a=read();
		printf("%d\n",f[a]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34