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

大致题意 📖

牛牛即将要参加考试，他学会了填答题卡。

可惜他竖着的答题卡填成了横着的 : (

好奇的他想知道对于 n 道题，每道题 n 个选项的答题卡 ( n * n 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。

注：每道题只能选择一个选项，即 n * n 的矩阵中只能涂黑 n 个空。求横竖对称的方案数。

链接 🔗

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

题解 ❓

一种比较傻的办法吧，但应该也很好理解

观察图形发现，合法的图形一定是在关于 左上 -> 右下 这条线对称
并且如果选取了斜线以外的点，则它的对称点也唯一对称，因此会确定两个数

于是我们考虑枚举斜线上点的数量，然后再从剩下的点中求每次拿两个，不同情况的方案数

斜线上有i个点的方案数为 ，然后非斜线上的点数为
当然，这题需要判断下，如果为奇数则要continue
然后后面这个东西应该是有公式的，但因为比较笨，就直接对 做了个前缀和
F[n],也就是不停的取2个
当然这肯定会有重复，比如先取14，32和32，14,这里会被重复计算两次，也就是顺序前后不同会被重复统计
发现会被分成个块，这些块有种不同排列，因此要去掉
答案就是

代码

ll fpow(ll a,ll b,ll mod){ll res = 1ll;while(b){if(b&1) res = (res * a) %mod;a = (a * a) %mod;b >>=1;}return res;}
const int mod = 1e9+7;
const double eps = 1e-8;

const int N = 1e6+10;
struct
{
    ll fac[N],inv[N],Finv[N];
    void init()
    {
        fac[0] = 1ll, Finv[0]=1ll,inv[1]=1ll;
        for(int i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        for(int i=1;i<N;i++)
        {
            fac[i]=fac[i-1]*i%mod;
            Finv[i]=Finv[i-1]*inv[i]%mod;
        }
    }
    ll C(ll n,ll m)
    {
        if(n<0||m<0||m>n) return 0;
        if(m == 0 || n == m) return 1;
        return fac[n] * Finv[m] %mod * Finv[n-m] %mod;
    }
}O_O;
ll f[N];
int main()
{
//    __IN;__OUT;
    ll n;RLL(n);
    O_O.init();
    ll ans = 0;
    f[0] = 1;
    FOR(i,1,n) f[i] = f[i-1] * O_O.C(i*2,2) %mod;
    FOR(i,0,n)
    {
        if ((n - i) % 2 == 0)
        {
            ans += O_O.C(n, i) * O_O.fac[(n-i)] %mod  *fpow(O_O.fac[(n-i)/2],mod-2,mod) %mod;
            ans %= mod;
        }
    }

    PLN(ans);
    return 0;
}