牛客IOI周赛16-普及组 C
答题卡
http://www.nowcoder.com/questionTerminal/68d4cc423c824d5881ecb314c78f0d1d
Question
求让 的矩阵横竖对称的填法。（沿主对角线）
Solution 1
因为是沿主对角线对称。
所以我们考虑第一道题填涂的选项的位置
如果填
，第一道题填位置
则第1行和第1列都不可以再填涂。
所以只需要剩下的(n-1)*(n-1) 的矩阵对称即可
如果不填
则也要填
，第一题填位置
则第1行，第x行，第1列，第x列，都不可以再进行填涂。
所以只需要让其余的部分拼在一起的(n-2)*(n-2)的矩阵对称即可
表示
的矩阵横竖对称的填法。
则
Solution 2
题（手动狗头），列举出
的方案数，然后可以找到一个序列。
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696 ...
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9 + 7;
const int MAX_N=1e5 + 5;
int n;
ll f[MAX_N];
int main(){
cin>>n;
f[0]=f[1]=1;
for(int i=2;i<=n;i++) f[i]=(f[i-1]+(i-1)*f[i-2])%mod;
printf("%d",f[n]);
return 0;
} 
查看20道真题和解析
