Day4.
I think my barriers of programming are gone, if I keep this training for 90 days.
Let's try 4th Problem. This one is easy one.
Code is below.
H, W = map(int,input().split())
#入力を受け取る
Map =
#地図を入れるもの、かご
preprocess1 = [0 for _ in range(H)]
#H行の各行の総和を入れるかご
for i in range(H):
temp1 = list(map(int, input().split()))
#入力を受けつつ
preprocess1[i] = sum(temp1)
#総和を計算
Map.append(temp1)
preprocess2 = [0 for _ in range(W)]
#W列の各列の総和を入れるかご
for j in range(W):
for i in range(H):
preprocess2[j] += Map[i][j]
#総和を計算
New_Map = [[0] * W for _ in range(H)]
#新しい地図を作る
for i in range(H):
for j in range(W):
New_Map[i][j] = preprocess1[i] + preprocess2[j] - Map[i][j]
#包除原理 |A∪B|=|A|+|B|-|A∩B| のこと。
print(*New_Map[i])
- 今回はうまく包除原理を使おうという回だった。
- せっかくなので、包除原理について調べてみる。
- まずはこちら。
- いくつも集合があったとき、そのすべての和集合を、積集合の塊として表す式。
- 「総和集合=-∑(-1)^k(k個の部分積集合の総和)」
- または、よりも、かつ、の方が扱いやすいことが多い。
- 男、または、40歳以上
- 男か、40歳以上の女
- 男、かつ、40歳以上
- 40歳以上の男
- 男、または、40歳以上
- 二項定理による証明や、数学的帰納法による証明がある。
- さらに、こちらのスライドをまとめてみる。
N = int(input())
def get_prime_factor(n):
temp = n
prime_list =
devide = 2
while devide <= int(n**0.5):
if temp % devide == 0:
prime_list.append(devide)
while temp%devide == 0:
temp //= devide
devide += 1
else:
if temp != 1:
prime_list.append(temp)
return prime_list
def Euler(n):
all_prime = get_prime_factor(n)
m = len(all_prime)
answer = 0
for i in range(2**m):
sub_prime = []
for j in range(m): # このループが一番のポイント
if ((i >> j) & 1):
sub_prime.append(all_prime[j])
k = len(sub_prime)
product = 1
if k==0:
continue
for l in range(k):
product *= sub_prime[l]
answer += (-1)**(k-1)*(n//product)
return (n-answer, all_prime)
Euler(N)
#get_prime_factor(N)
- 続きから始める
- Uncommon
- さっきのオイラー関数の話をなんども繰り返すだけ。
- コードはパス
- Ball and Boxes
- この話が、こちらのサイトの話と繋がる。
- n人を区別のあるk個のチームに分ける場合の数
- 10人を3つに分ける場合、
- これは、補集合の考え方を採用して、
- 10人が3つのどれかに入る
- 10人が2つのどれかに入る
- 10人が1つに入る
- の足し引きで求まる。
- これは、補集合の考え方を採用して、
- これを、区別のないグループにすると、スターリング数になる。
- kの階乗で割るだけ。
- 区別のないk個以下のグループに分ける方法の数をベル数という。
- スターリング数を足していく
- この問題の肝は、うまく対称性を利用して、Combinationでまとめて計算できる点でうれしい。
- これは、n個からk個選んだ集合同士の重なりの部分(intersection)の要素数が全て等しいから。
- Lahub and Permutations
- Uncommon
バイバイ!