牛客IOI周赛16-普及组 C

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;
}