Herhangi Matematiksel Şeyler: Euler Projesi 270. Soru

Kare kesme

Tam sayı N × N boyutlu kare bir kağıt parçası, bir köşesi başlangıç noktasında ve iki kenarı da x ve y eksenleri üzerinde olacak şekilde yerleştiriliyor. Ardından aşağıdaki kurallara uyarak bu kareyi kesiyoruz:

Sadece karenin farklı kenarlarında bulunan ve tam sayı koordinatlarına sahip iki nokta arasında uzanan düz kesimler yapıyoruz.
İki kesim kesişemez, ancak kesimler aynı kenar noktasında buluşabilir.
Daha fazla kurallı kesme yapılamayana kadar kesmeye devam edin.

Herhangi bir yansımayı veya dönüşümü farklı sayarsak, N x N karesini kesme yollarının sayısını C(N) ile tanımlayalım. Örneğin C(1) = 2 ve C(2) = 30 (aşağıda gösterilmiştir).

C(30) mod 10⁸ kaçtır?

Cevap: 82282080

C/C++:
#include <stdio.h>

#define N 30
#define LIMIT 100000000

long long int answer;

long long int tri[N][N];
long long int dia[N][N];
long long int dib[N][N];
long long int dic[N][N];

int find_tri();
int find_d1();
int find_d2();
int find_d3();

int main(int argc, char **argv) {
  int i, j;

find_tri();
  find_d3();
  find_d1();
  find_d2();

answer = dib[N-2][N-2];
  for (i=0; i<N-1; i++) {
    answer += tri[N-1][i]*dia[N-2][N-1-i-1];
    answer %= LIMIT;
  }
  answer += tri[N-1][N-1]*tri[N-2][N-1];
  answer %= LIMIT;
  for (i=0; i<N-1; i++) {
    answer += tri[N-2][i]*dia[N-1][N-1-i-1];
    answer %= LIMIT;
  }

printf ("answer: %lld\n", answer);
}

int find_tri() {
  int i, j, k;
 
  for (i=0; i<N; i++) {
    tri[0][i] = 1;
    tri[i][0] = 1;
  }
  for (i=1; i<N; i++)
    for (j=i; j<N; j++) {
      for (k=0;k<=i; k++) {
 tri[i][j] += tri[k][j-1];
 tri[i][j] %= LIMIT;
      }
      tri[j][i] = tri[i][j];
    }
}

int find_d1() {
  int i, j, k;
 
  for (i=0; i<N-1; i++)
    for (j=i; j<N; j++) {
      if (i==0) {
 dia[i][j] = dic[N-2][j];
 for (k=0; k<=j; k++)
   dia[i][j] += tri[N-1][k];
      } else {
 dia[i][j] = tri[i-1][N-1];
 for (k=0; k<N-1; k++) {
   dia[i][j] += tri[i-1][N-2-k]*dic[k][j];
   dia[i][j] %= LIMIT;
 }
 for (k=0; k<=j; k++)
   dia[i][j] += dia[i-1][k];
      }
 
      dia[i][j] %= LIMIT;
      dia[j][i] = dia[i][j];
    }
}

int find_d2() {
  int i, j, k;

for (i=0; i<N-1; i++)
    for (j=i; j<N-1; j++) {
      if (i==0)
 dib[i][j] = dia[j][N-1];
      else
 dib[i][j] = dib[i-1][j];

dib[i][j] %= LIMIT;
      if (j==0)
 dib[i][j] += dia[i][N-1];
      else
 dib[i][j] += dib[i][j-1];
      dib[i][j] %= LIMIT;

for (k=0; k<N-1; k++) {
 dib[i][j] += tri[i][k]* dia[j][N-2-k];
 dib[i][j] %= LIMIT;
 dib[i][j] += tri[j][k]* dia[i][N-2-k];
 dib[i][j] %= LIMIT;
      }
      dib[i][j] += tri[i][N-1]*tri[j][N-1];

dib[i][j] %= LIMIT;
      dib[j][i] = dib[i][j];
    }
}

int find_d3() {
  int i, j, k;

for (i=0; i<N-1; i++)
    for (j=0; j<N; j++) {
      if (i==0)
 dic[i][j] = 1;
      else
 dic[i][j] = dic[i-1][j];
      for (k=0; k<=j; k++) {
 dic[i][j] += tri[i][k];
 dic[i][j] %= LIMIT;
      }
    }
}

Python:
def normalize(p):
    kmax = -1
    max_len = 0
    for k in range(len(p)):
        if p[k] > max_len:
            kmax = k
            max_len = p[k]
    
    return p[kmax:] + p[:kmax]

def divide_polygon(p, pt1, pt2):
    e1, v1 = pt1
    e2, v2 = pt2
    if v1 == 0:
        if v2 == 0:
            return p[e1:e2] + (1,), p[e2:] + p[:e1] + (1,)
        else:
            return p[e1:e2] + (v2, 1), (p[e2] - v2,) + p[e2+1:] + p[:e1] + (1,)
    else:
        if v2 == 0:
            return (p[e1] - v1,) + p[e1+1:e2] + (1,), p[e2:] + p[:e1] + (v1, 1)
        else:
            return (p[e1] - v1,) + p[e1+1:e2] + (v2, 1), \
                        (p[e2] - v2,) + p[e2+1:] + p[:e1] + (v1, 1)

def is_on_same_edge(pt1, pt2, p):
    n = len(p)
    e1, v1 = pt1
    e2, v2 = pt2
    if e1 == e2:
        return True
    elif e1 == 0 and e2 == n - 1 and v1 == 0:
        return True
    elif e1 == e2 + 1 and v1 == 0:
        return True
    elif e2 == 0 and e1 == n - 1 and v2 == 0:
        return True
    elif e2 == e1 + 1 and v2 == 0:
        return True
    else:
        return False

def gen_points(p):
    for k in range(1, len(p) - 1):
        for l in range(p[k]):
            if k != 1 or l != 0:
                yield k, l

def right_neighbor(p, pt):
    e1, v1 = pt
    if v1 < p[e1] - 1:
        return e1, v1 + 1
    else:
        if e1 < len(p) - 1:
            return e1 + 1, 0
        else:
            return 0, 0

def left_neighbor(p, pt):
    e1, v1 = pt
    if v1 > 0:
        return e1, v1 - 1
    else:
        if e1 > 0:
            return e1 - 1, p[e1-1] - 1
        else:
            return len(p) - 1, p[-1] - 1

def count(p):
    if p == (1, 1, 1) or p == ():
        return 1
    
    p = normalize(p)
    if p in dic:
        return dic[p]
    
    # II)
    s = 0
    pt0 = (0, 0)
    pt1 = right_neighbor(p, pt0)
    e1, v1 = pt1
    for pt2 in gen_points(p):
        e2, v2 = pt2
        if v1 == 0 and is_on_same_edge(pt1, pt2, p):
            p1 = ()
            p2, p3 = divide_polygon(p, pt0, pt2)
        else:
            p2, p3 = divide_polygon(p, pt0, pt2)
            if p2[e2] == v2:
                pt2 = (e2 + 1, 0)
            p1, p2 = divide_polygon(p2, pt1, pt2)
        s += count(p1) * count(p2) * count(p3)
    
    # I)
    pt2 = left_neighbor(p, pt0)
    p4, p5 = divide_polygon(p, pt1, pt2)
    s += count(p4)
    
    s = s % 10 ** 8
    dic[p] = s
    return s

def C(n):
    return count((n, n, n, n))

N = 30
dic = { }
print C(N)

ml:
let answer n =
 let (+:) a b = (a+:b) %: 100000000L
 and ( *: ) a b = (a*:b) %: 100000000L in
 memo (fun f (x,y) -> if y=x+1 then 1L else 
  if y=x+2 then if (x+1) mod n = 0 then 1L else 0L else
  let w = if x=0 && y=4*n-1 then 3*n else y in 
  let rec g s z = if z=w then s else g (s+: f (x,z) *: f (z,y)) (z+1) in 
  g 0L (x+1))
 (0,4*n-1)

Haskell:
import Data.MemoTrie (memo2)

choose, memoC :: Integer -> Integer -> Integer
choose n r = div (product [n-r+1..n]) $ product [1..r]
memoC = memo2 choose

trapezoid :: Integer -> Integer -> Integer -> Integer
trapezoid n 1 0 = 1
trapezoid n (u+1) 0 = sum [memoC (k+u-2) (u-1) | k <- [1..n-1]]
trapezoid n 0 l = trapezoid n l 0
trapezoid n u l = sum [memoC (k+u-2) (u-1) * memoC (n-k+l-2) (l-1) | k <- [1..n-1]]

p270 :: Integer -> Integer
p270 n = 2 * sum [count u1 u2 l1 l2 | u1 <- [0..n], l1 <- [0..n], u1 > 0 || l1 > 0,
                  u2 <- [0..n-u1], l2 <- [0..n-l1], u1+u2 < n || l1+l2 < n]
         - 4 * sum [count u1 u2 0 0 | u1 <- [1..n-1], u2 <- [0..n-u1-1]]
         - 2 * (sum [memoT 0 u| u <- [1..n]] ^ 2)
    where count u1 u2 l1 l2 = memoT u1 l1 * memoC (u2 + l2) l2 * memoT (n - u1 - u2) (n - l1 - l2)
          memoT = memo2 (trapezoid n)

main :: IO ()
main = print.(`mod` 10^8) $ p270 30

Ruby:
$size = 30
fig = (1.. $size).map{|i|[0,i]} +
      (1.. $size).map{|i|[i,$size]} +
      (0...$size).map{|i|[$size,i]}.reverse +
      (0...$size).map{|i|[i,0]}.reverse

def cab a,b
    ((a+1)..b).inject{|i,j|i*j} /
    (1..(b-a)).inject{|i,j|i*j}
end

$htre = {}
def tre a,b
    a,b = b,a if a>b
    return 1 if a == 1
    return b if a == 2
    x = $size*a+b
    return $htre[x] if $htre[x]
    $htre[x] = cab a-1,a-2+b
end

$htra = {}
def tra a,b
    x = $size*a+b
    return $htra[x] if $htra[x]
    $htra[x] = 
    (a == 1 ? tre(b,$size) : tra(a-1,b)) +
    (b == 1 ? tre(a,$size) : tra(a,b-1)) +
    (1...$size).inject(0) { |i,j| i + tre(a,j) * tre($size-j,b) }
end

$counter = 0
$hfig = {}
def f fig
    x = fig.flatten.hash
    return $hfig[x] if $hfig[x]
    $hfig[x] = ((1 == $counter += 1) ? 0 :
    (fig[0][1] == $size-1 ? tra($size-fig[-1][0],$size) : f(fig[1..-1]))) +
    (fig[-1][0] == $size-1 ? tra($size-fig[0][1],$size) : f(fig[0..-2])) +
    tre($size-fig[0][1],$size) * tre($size-fig[-1][0],$size) +
    (1...$size).inject(0) { |i,j| i +
        tre($size-fig[-1][0],j) *
        tra($size-fig[0][1],$size-j) +
        tre($size-fig[0][1],j) *
        tra($size-fig[-1][0],$size-j) }
end

p f(fig)

C#:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Drawing;
using System.IO;

using MathUtilities;

namespace MathProblems
{
    public class Problem270
    {
        /// <summary>
        /// Problem270 - Cutting Squares
        /// </summary>
        /// <remarks>
        /// The problem is equivalent to counting the number of triangulations of the square.
        /// The approach is DP via recursion and memoization.  Note that if we consider the
        /// origin, the set of cuts partition into those that radiate from the origin and
        /// those that do not.
        /// 
        /// Consider cuts radiating from the origin to the lower right of the figure, and
        /// proceeding counter-clockwise.  For each such cut, we partition the current figure
        /// into a left figure and a right figure, the shapes of which depend on the current figure
        /// and the location of the cut.  Then the count of all triangulations that include
        /// that particular cut is the count of triangulations of the left figure times the
        /// count of triangulations of the right figure, with the qualification that the
        /// count for the right figure must exclude any cuts radiating from the origin, as
        /// those would already have been counted.
        /// 
        /// The figures that can result during the cutting process are triangles (which always
        /// have one side of 1, so only two sides need be specified), quadrilaterals,
        /// "notched" pentagons (which look like a rectangle with one corner cut off) and
        /// "double notched" pentagons (which look like a rectangle with two adjacent corners cut off).
        /// The cutting process is managed so the notches never have interior points.
        /// </remarks>
        public void Run()
        {
            long mod = 100000000;

int size = 30;

Console.WriteLine("Number of ways to cut a {0}x{0} square:  {1}", size, C(size, mod));
        }

long C(int n, long mod)
        {
            return CQuad(n, n, n, n, false, mod);
        }

Dictionary<int, long> quadCache = new Dictionary<int, long>();

long CQuad(int n, int m, int p, int q, bool noCutsFromOrigin, long mod)
        {
            if (noCutsFromOrigin)
                return CNotch(n - 1, m, p, q - 1, false, mod);

int key = n << 25 | m << 17 | p << 9 | q << 1 | (noCutsFromOrigin ? 1 : 0);
            long count;
            if (quadCache.TryGetValue(key, out count))
                return count;

// Count cases where there is no cut radiating from the origin.
            count = CNotch(n - 1, m, p, q - 1, false, mod);

// Count cases where there is a cut from the origin to the right side.
            for (int i = 1; i <= m - 1; i++)
            {
                long term = CQuad(1, m - i, p, q, false, mod) * CTriangle(n, i, true, mod);
                count = (count + term % mod) % mod;
            }

// Count the case where the cut goes to the upper right corner.
            count = (count + (CTriangle(p, q, false, mod) * CTriangle(n, m, true, mod)) % mod) % mod;

// Count cases where the cut goes from the origin to the top side.
            for (int i = 1; i <= p - 1; i++)
            {
                long term = CTriangle(q, p - i, false, mod) * CQuad(n, m, i, 1, true, mod);
                count = (count + term % mod) % mod;
            }

quadCache[key] = count;
            return count;
        }

Dictionary<int, long> triangleCache = new Dictionary<int, long>();

long CTriangle(int n, int m, bool noCutsFromOrigin, long mod)
        {
            if (n == 1)
                return (noCutsFromOrigin && m > 1) ? 0 : 1;

if (noCutsFromOrigin)
                return CTriangle(n - 1, m, false, mod);

int key = n << 25 | m << 17 | (noCutsFromOrigin ? 1 : 0);
            long count;
            if (triangleCache.TryGetValue(key, out count))
                return count;

count = CTriangle(n - 1, m, false, mod);
            for (int i = 1; i <= m - 1; i++)
            {
                long term = CTriangle(1, m - i, false, mod) * CTriangle(n, i, true, mod);
                count = (count + term % mod) % mod;
            }

triangleCache[key] = count;
            return count;
        }

Dictionary<int, long> notchCache = new Dictionary<int, long>();

long CNotch(int n, int m, int p, int q, bool noCutsFromOrigin, long mod)
        {
            if (noCutsFromOrigin)
                return CNotch(n - 1, m, p, q, false, mod);

if (n == 0)
                if (q == 0)
                    return CTriangle(m, p, false, mod);
                else
                    return CQuad(1, m, p, q, false, mod);
            else
                if (q == 0)
                    return CQuad(n, m, p, 1, false, mod);

int key = n << 25 | m << 17 | p << 9 | q << 1 | (noCutsFromOrigin ? 1 : 0);
            long count;
            if (notchCache.TryGetValue(key, out count))
                return count;

count = CNotch(n - 1, m, p, q, false, mod);

for (int i = 1; i <= m - 1; i++)
            {
                long term = CDoubleNotch(m - i, p, q, false, mod) * CTriangle(n, i, true, mod);
                count = (count + term % mod) % mod;
            }

count = (count + (CQuad(1, 1, p, q, false, mod) * CTriangle(n, m, true, mod)) % mod) % mod;

for (int i = 1; i <= p - 1; i++)
            {
                long term = CQuad(1, 1, p - i, q, false, mod) * CQuad(n, m, i, 1, true, mod);
                count = (count + term % mod) % mod;
            }

count = (count + (CTriangle(1, q, false, mod) * CQuad(n, m, p, 1, true, mod)) % mod) % mod;

for (int i = 1; i <= q - 1; i++)
            {
                long term = CTriangle(1, i, false, mod) * CNotch(n, m, p, i, true, mod);
                count = (count + term % mod) % mod;
            }

notchCache[key] = count;
            return count;
        }

Dictionary<int, long> doubleNotchCache = new Dictionary<int, long>();

long CDoubleNotch(int m, int p, int q, bool noCutsFromOrigin, long mod)
        {
            int key = m << 17 | p << 9 | q << 1 | (noCutsFromOrigin ? 1 : 0);
            long count;
            if (doubleNotchCache.TryGetValue(key, out count))
                return count;

if (noCutsFromOrigin)
                count = CQuad(1, m, p, q, false, mod);
            else
            {
                count = CQuad(1, m, p, q, false, mod);

for (int i = 1; i <= m - 1; i++)
                {
                    long term = CDoubleNotch(m - i, p, q, false, mod) * CTriangle(1, i, true, mod);
                    count = (count + term % mod) % mod;
                }

count = (count + (CQuad(1, 1, p, q, false, mod) * CTriangle(1, m, true, mod)) % mod) % mod;

for (int i = 1; i <= p - 1; i++)
                {
                    long term = CQuad(1, 1, p - i, q, false, mod) * CQuad(1, m, i, 1, true, mod);
                    count = (count + term % mod) % mod;
                }

count = (count + (CTriangle(1, q, false, mod) * CQuad(1, m, p, 1, true, mod)) % mod) % mod;

for (int i = 1; i <= q - 1; i++)
                {
                    long term = CTriangle(1, q - i, false, mod) * CDoubleNotch(m, p, i, true, mod);
                    count = (count + term % mod) % mod;
                }
            }

doubleNotchCache[key] = count;
            return count;
        }
    }
}

Herhangi Matematiksel Şeyler

Sayfalar

5 Ağustos 2019

Euler Projesi 270. Soru