递推，CF 1957C - How Does the Rook Move?

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1957C - How Does the Rook Move?

---

二、解题报告

1、思路分析

规则就是八皇后问题的规则，我们考虑第一行第一列选哪一个？

如果选(1, 1)，那么问题等价于 (n - 1) * (n - 1) 网格的方案数

如果选其他的(1, x) / (x, 1) x > 1，那么会扣掉一行一列，问题等价于 (n - 2) * (n - 2)的网格的方案数

我们定义f(i) 为 i * i 网格的方案数，那么f 我们可以得到递推式：

f(i) = f(i - 1) + (2i - 2) * f(i - 2)，2i - 2是第一行第一列除去 (1, 1) 剩下的格子数目

f(i) 我们可以预处理

对于初始的 k 个操作，如果是对角线，那么n-1，否则n-2，然后输出f[n] 即可

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

 ​

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Template;

Solution s = new();
s.Solve();

namespace Template
{
    internal class Solution
    {
        private readonly string FILEPATH = "in.txt";
#if LOCAL
        private readonly StreamReader sr = new(FILEPATH);
#else
        private readonly StreamReader sr = new(Console.OpenStandardInput());
#endif
        private T Read<T>()
            where T : struct, IConvertible
        {
            char c;
            dynamic res = default(T);
            dynamic sign = 1;
            while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read();
            if (!sr.EndOfStream && (char)sr.Peek() == '-')
            {
                sr.Read();
                sign = -1;
            }
            while (!sr.EndOfStream && char.IsDigit((char)sr.Peek()))
            {
                c = (char)sr.Read();
                res = res * 10 + c - '0';
            }
            return res * sign;
        }

        private T[] ReadArray<T>(int n)
            where T : struct, IConvertible
        {
            T[] arr = new T[n];
            for (int i = 0; i < n; ++i) arr[i] = Read<T>();
            return arr;
        }
        public void Solve()
        {
            StringBuilder output = new();
            const int P = 1_000_000_007;
            const int N = 300000;
            int[] f = new int[N + 1];
            f[0] = f[1] = 1;
            for (int i = 2; i <= N; ++i)
            {
                f[i] = (int)((f[i - 1] + 2L * (i - 1) * f[i - 2] % P) % P);
            }

            int T = Read<int>();
            while (T -- > 0)
            {
                int n = Read<int>(), k = Read<int>();
                for (int i = 0; i < k; ++ i)
                {
                    int r = Read<int>(), c = Read<int>();
                    n -= (r == c ? 1 : 2);
                }

                output.Append(f[n]).AppendLine();
            }

            Console.Write(output.ToString());
        }
    }
}

原文地址：https://blog.csdn.net/EQUINOX1/article/details/142889128

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！