logoChat01.ai

Внимательно изучи данные картинки и реши это задан...

تم الإنشاء في: ٢٦ يناير ٢٠٢٦

تمت الإجابة باستخدام GPT-5.2 Thinking بواسطة Chat01

سؤال

image.pngimage.png
image.pngimage.png
image.pngimage.png

Внимательно изучи данные картинки и реши это задание на C# только со встроенными библиотеками

Python

python
import itertools, math
def count_bishops(n,k):
    cells=[(r,c) for r in range(n) for c in range(n)]
    mod=10**9+7
    cnt=0
    for comb in itertools.combinations(cells,k):
        ok=True
        # check bishop attacks: same diagonal r-c or r+c
        seen1=set()
        seen2=set()
        for r,c in comb:
            d1=r-c
            d2=r+c
            if d1 in seen1 or d2 in seen2:
                ok=False;break
            seen1.add(d1);seen2.add(d2)
        if ok: cnt+=1
    return cnt
for n in range(1,6):
    for k in range(0,2*n):
        if n<=6:
            print(n,k,count_bishops(n,k))
    print()

Python

python
def count_color(n, k, color):  # color=0 for even parity (r+c)%2==0
    cells=[(r,c) for r in range(n) for c in range(n) if (r+c)%2==color]
    cnt=0
    for comb in itertools.combinations(cells,k):
        ok=True
        d1=set(); d2=set()
        for r,c in comb:
            if (r-c) in d1 or (r+c) in d2:
                ok=False;break
            d1.add(r-c);d2.add(r+c)
        if ok: cnt+=1
    return cnt

def color_poly(n,color):
    maxk=2*n # enough
    res=[]
    for k in range(0,2*n):
        res.append(count_color(n,k,color))
    return res
for n in [5]:
    for color in [0,1]:
        poly=color_poly(n,color)
        print(n,color,poly

Python

python
def rook_poly(lengths):
    m=len(lengths)
    dp=[0]*(m+1)
    dp[0]=1
    for L in lengths:
        for j in range(m,0,-1):
            dp[j]+=dp[j-1]*(L - (j-1))
    return dp
print(rook_poly([1,1,3,3,5])[:5])

Python

python
print(rook_poly([2,2,4,4])[:5])

Python

python
def diag_lengths_color(n):
    # NW-SE diagonals indexed by r-c = t from -(n-1) to n-1
    lengths={0:[],1:[]}
    for t in range(-(n-1), n):
        # squares (r,c) with r-c=t
        cells=[(r,c) for r in range(n) for c in range(n) if r-c==t]
        L=len(cells)
        col=(cells[0][0]+cells[0][1])%2
        lengths[col].append(L)
    for col in lengths:
        lengths[col].sort()
    return lengths
for n in range(2,7):
    print(n, diag_lengths_color(n))

Python

python
def poly_color(n,color,kmax):
    lst=[]
    for t in range(-(n-1), n):
        L=n-abs(t)
        if (t&1)==color:
            lst.append(L)
    lst.sort()
    K=min(kmax,len(lst))
    dp=[0]*(K+1); dp[0]=1
    rows=0
    for L in lst:
        rows+=1
        upto=min(K, rows)
        for j in range(upto,0,-1):
            ways=L - (j-1)
            if ways>0:
                dp[j]=(dp[j]+dp[j-1]*ways)%MOD
    return dp

def count_formula(n,k):
    kmax=min(k,n) # for each
    a=poly_color(n,0,kmax)
    b=poly_color(n,1,kmax)
    ans=0
    for i in range(0, min(k, len(a)-1)+1):
        j=k-i
        if 0<=j<=len(b)-1:
            ans=(ans+a[i]*b[j])%MOD
    return ans

for n in range(1,8):
    for k in range(0,2*n):
        brute=count_bishops(n,k)
        formula=count_formula(n,k)
        if brute!=formula:
            print("Mismatch",n,k,brute,formula)
            raise SystemExit
print("all ok")

Python

python
for n in range(1,7):
    for k in range(0,2*n):
        brute=count_bishops(n,k)
        formula=count_formula(n,k)
        if brute!=formula:
            print("Mismatch",n,k,brute,formula)
            break
    else:
        continue
    break
print("done")

Python

python
for n in range(1,6):
    for k in range(0,2*n):
        brute=count_bishops(n,k)
        formula=count_formula(n,k)
        if brute!=formula:
            print("Mismatch",n,k,brute,formula)
            raise SystemExit
print("all ok up to 5")

الفكرة

Crafting explanation for the recurrence

The formula works, so now I’ll explain the recurrence. Bishops move diagonally and maintain their color, so they’re independent between colors. Fixing one color, I’ll focus on diagonals in one direction (NW-SE). Placing non-attacking bishops is like placing rooks, using intersections of diagonals. This leads to a Ferrers board setup.

Explaining the DP computation for rooks placement

To calculate the number of ways to place J rooks, we use dynamic programming (DP). For each row, we either skip it (leaving the DP state unchanged) or place a rook in an available column. Free columns depend on how many rooks are already placed in previous rows. After sorting diagonals by length, we apply the formula for each color using two lists: one for even offsets and one for odd offsets.

Formula approach and early termination

We can compute the solution using a formula for each offset (t from -(n-1) to n-1), considering the color using bitwise operations. The formula involves sorting each list and calculating the possible placements. To optimize, we handle cases where k exceeds the maximum possible placements early on and avoid unnecessary loops by implementing early termination, especially for larger n values. The main check for k values greater than the limit brings a quick exit. I'll also avoid LINQ in critical performance loops in my C# implementation.

Implementing BuildPoly function

The function iterates through each length to update the dp array based on possible ways to place rooks. For performance, it's important to keep K within bounds, by setting it to the minimum of k or the length of the current list. After calculating the dp values for each color-coded length, the final result is obtained by multiplying the results from different arrays (poly0 and poly1) with care for large k values, ensuring the loop remains manageable even when k is large.

Thought for 9m 11s

الإجابة

Идея

Слон всегда остаётся на клетках одного цвета, поэтому расстановки на чёрных и белых клетках независимы:

Ans(k)=∑i=0kBlack[i]⋅White[k−i](mod109+7)Ans(k)=\sum_{i=0}^{k} \text{Black}[i]\cdot \text{White}[k-i] \pmod{10^9+7}

Для фиксированного цвета каждая NW-SE диагональ (с постоянным r−cr-c) одноцветная и имеет длину
  L=n−∣r−c∣\;L = n - |r-c|. На одной такой диагонали можно поставить не больше одного слона.

Если отсортировать длины диагоналей данного цвета по неубыванию, то число способов поставить jj слонов считается “как ладьи на феррерсовой доске” DP:

  • dp[j] — способов поставить j слонов, обработав несколько диагоналей.
  • Для диагонали длины L:
    • не ставим: dp[j] остаётся
    • ставим: есть L - (j-1) вариантов (занято уже j-1 разных “перпендикулярных” диагоналей)
dp[j]+=dp[j−1]⋅(L−(j−1))dp[j] \mathrel{+}= dp[j-1]\cdot (L-(j-1))

Максимум неатакующих слонов на доске при n>1n>1 равен 2n−22n-2. Если kk больше — ответ 0.

Решение на C# (только стандартные библиотеки)

csharp
using System;
using System.Collections.Generic;
using System.IO;

public class Program
{
    const long MOD = 1_000_000_007L;

    static void Main()
    {
        var fs = new FastScanner(Console.OpenStandardInput());
        int n = fs.NextInt();
        int k = fs.NextInt();

        int maxPossible = (n == 1) ? 1 : 2 * n - 2;
        if (k > maxPossible)
        {
            Console.WriteLine(0);
            return;
        }

        // Собираем длины NW-SE диагоналей по цветам.
        // Диагональ задаётся t = r - c, t in [-(n-1)..(n-1)], длина = n - |t|.
        // Цвет клетки на диагонали определяется чётностью t (потому что (r+c) и (r-c) одной чётности).
        var lens0 = new List<int>();
        var lens1 = new List<int>();

        for (int t = -(n - 1); t <= (n - 1); t++)
        {
            int len = n - Math.Abs(t);
            int color = t & 1; // работает и для отрицательных t
            if (color == 0) lens0.Add(len);
            else lens1.Add(len);
        }

        lens0.Sort();
        lens1.Sort();

        // Нам нужны коэффициенты только до k, но реально максимум на цвет <= n.
        int K0 = Math.Min(k, lens0.Count);
        int K1 = Math.Min(k, lens1.Count);

        long[] poly0 = BuildPoly(lens0, K0);
        long[] poly1 = BuildPoly(lens1, K1);

        long ans = 0;
        int maxI = Math.Min(k, poly0.Length - 1);
        for (int i = 0; i <= maxI; i++)
        {
            int j = k - i;
            if (j >= 0 && j < poly1.Length)
            {
                ans = (ans + poly0[i] * poly1[j]) % MOD;
            }
        }

        Console.WriteLine(ans);
    }

    // DP по диагоналям (в порядке неубывания длины).
    // dp[j] = ways to place j bishops on this color.
    static long[] BuildPoly(List<int> lens, int K)
    {
        long[] dp = new long[K + 1];
        dp[0] = 1;

        int processed = 0;
        foreach (int L in lens)
        {
            processed++;
            int upto = Math.Min(K, processed);
            for (int j = upto; j >= 1; j--)
            {
                int ways = L - (j - 1);
                if (ways > 0)
                {
                    dp[j] = (dp[j] + dp[j - 1] * ways) % MOD;
                }
            }
        }
        return dp;
    }

    // Мини-сканер (быстро и без LINQ)
    sealed class FastScanner
    {
        private readonly Stream _s;
        private readonly byte[] _buf = new byte[1 << 16];
        private int _len, _ptr;

        public FastScanner(Stream s) { _s = s; }

        private int Read()
        {
            if (_ptr >= _len)
            {
                _len = _s.Read(_buf, 0, _buf.Length);
                _ptr = 0;
                if (_len <= 0) return -1;
            }
            return _buf[_ptr++];
        }

        public int NextInt()
        {
            int c;
            do c = Read(); while (c <= ' ');

            int sign = 1;
            if (c == '-')
            {
                sign = -1;
                c = Read();
            }

            int x = 0;
            while (c > ' ')
            {
                x = x * 10 + (c - '0');
                c = Read();
            }
            return x * sign;
        }
    }
}

Если хочешь — могу кратко показать, как именно формируются списки длин диагоналей для каждого цвета на примере n=5n=5 и почему DP даёт ровно те коэффициенты, которые потом свёртываются в ответ.

مشاركة هذا السؤال والجواب