牛客IOI周赛16-普及组 C 答题卡

Solution

先给一个非常规的解法, 打暴力找

直接看 (公式), 有
这时候点进去找 是什么, 得到下面结果
令
有递推式子
于是

打暴力Code

int ans, n;
int maze[105][105];
void dfs(int x) {
  if(x == n + 1) {
    int flag = 0;
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        if(maze[i][j] != maze[j][i]) {
          flag = 1;
        }
      }
    }
    if(!flag) ans++;
    return ;
  }
  for(int i = 1; i <= n; i++) {
    maze[x][i] = 1;
    dfs(x + 1);
    maze[x][i] = 0;
  }
}

Code

/*
  autor: Kurisu
  2020年4月30日16:48:49
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 1e5 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;
int n;
ll fun(ll x) {
  return x >= mod ? x % mod : x;
}
ll dp[N];
int main() {
  scanf("%d", &n);
  dp[2] = 1, dp[3] = 3;
  for(int i = 4; i <= n; i++) {
    dp[i] = fun(dp[i - 1] + (1 + dp[i - 2]) * (i - 1));
  }
  printf("%lld\n", dp[n] + 1);
  return 0;
}
// 3 + 2 * 3 = 9