. のとき左から $i$ 個目の石が白、# のとき黒
最終状態から考えると、'#.'という箇所が1箇所でもあるとダメなので、ある場所に黒が現れたら、そこから右は全て黒になるしか無い。
......#######
こんな感じになる。 境界が $N+1$ 通り考えられるので、全て試して、最も少ないのが答え。
塗り替える石は「最終的に白になるのに初期状態が黒」「黒になるのに初期状態が白」の合計なので、
#の数.の数を別々に計算して、合計する。
S = . # # . . . # # # .
i 0 1 2 3 4 5 6 7 8 9 10 .と#の境界候補
---------------------------
→ 0 0 1 2 2 2 2 3 4 5 5 現れた # の数（iが境界だったら、#から.に塗り替えなくてはいけない石の数）
← 5 4 4 4 3 2 1 1 1 1 0 現れた . の数（iが境界だったら、.から#に塗り替えなくてはいけない石の数）
計 5 4 5 6 5 4 3 4 5 6 5
^------------ここが最小
. . . . . . # # # # 最終状態はこうなる
n = int(input())
s = input()
f = [0]
tmp = 0
for c in s:
if c == '#':
tmp += 1
f.append(tmp)
b = [0]
tmp = 0
for c in s[::-1]:
if c == '.':
tmp += 1
b.append(tmp)
b.reverse()
print(min(map(sum, zip(f, b))))
正の面積を持つ三角形とは、つまり、一番長い辺 $A$ とそれ以外の2辺 $B,C$ が、$A \lt B+C$ となっているということである。 （一番長い辺が他の2辺の合計より長かったら、三角形を作れない）
包除で求める対象を考察した後、DPで具体的な数を数え上げる。
条件を満たす組み合わせは3辺がバランスよく配分されてないといけないが、「バランスよい状態」を直接求めるのは難しいことがある。 逆に極端な組み合わせは求めやすく、それを全体から引くと上手くいく、この問題はそういうタイプである。
整数全体の和を $S$ とすると、三角形が出来ないとき、どれか1辺が $\frac{S}{2}$ 以上である。
なので、どれか1辺に $\frac{S}{2}$ 以上の整数が集中してしまう組み合わせの数を求めて全体から引けばよい。
┌ 3色の塗り分け方全体 ────┐ R >= S/2 となる塗り分け方の集合を Ro と表す │ ┌ R >= S/2 ┐ │ │ │ ┌─┼────┐ │ 答え = 全体 │ ┌┼───┼┐│ │ │ - Ro - Go - Bo │ │└───┼┼┘ │ │ + (Ro∩Go) + (Go∩Bo) + (Bo∩Ro) │ │ └┼ B >= S/2 ┘ │ - (Ro∩Go∩Bo) │ └ G >= S/2 ┘ │ └───────────────┘
ここで、R,G,Bは互いに入れ替えても組み合わせ数は変わらないので、最も長いのをRに固定して考える。
まず、Ro∩Go∩Bo は、R+G+B=S なのに3つともS/2以上というのはあり得ないので0通り。
Ro∩Goは、$R=G=\frac{S}{2},B=0$ ちょうどの時のみ。これは、$\frac{S}{2}$ になるような組み合わせ方が $K$ 通りあったとすると、Rの選び方を決めるとGも決まるので、$K$ 通り。
Roは、$R \ge \frac{S}{2}$ となる、ある1つの赤の塗り方が $L$ 本で達成されたとすると、残り $N-L$ 本を2つに振り分けるので、$2^{N-L}$ 通り。 これを全ての $R \ge \frac{S}{2}$ となる赤の塗り方で合計した値となる。
2種類のDPを用いる。
$DP1[i][k]$: $a_i$ まで見たところで、赤の合計が $k$ となるような、青、緑の塗り方も含めた場合の数
$DP2[i][k]$: $a_i$ まで見たところで、赤の合計が $k$ となるような、赤の塗り方だけに着目した場合の数（青、緑の塗り方は考慮しない）
DP2は言い換えれば「赤で塗らないのは必ず緑で塗る」場合の数とも言える。
最後まで進めて、先ほどの包除の式に以下を当てはめればよい
遷移自体はナップサック問題に似ている。$a_i$ だけずらしながら足し込むので、NumPyを使って高速化できる。逆に、NumPyを使わないと、Pythonでは厳しいか？
import sys
import numpy as np
n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353
s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.uint32)
dp2 = np.zeros(s + 1, dtype=np.uint32)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
dp1 = (dp1 * 2 + np.roll(dp1, a)) % MOD
dp2 = (dp2 + np.roll(dp2, a)) % MOD
h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
ans = (ans + dp2[h] * 3) % MOD
print(int(ans))
フェルマーの小定理を知っていることがほぼ前提となる。
$x^{p-1} \equiv 1 \mod{p}$ （ただし$x$と$p$は互いに素）
フェルマーの小定理より、$p-1$ ごとに、$x$ の係数はまとめることができる。
f(x) ＝ a9x^9 + a8x^8 + a7x^7 + a6x^6 + a5x^5 + a4x^4 + a3x^3 + a2x^2 + a1x + a0
≡ (a7 + a3) x^3 + (a6 + a2) x^2 + (a9 + a5 + a1) x + (a8 + a4 + a0) mod 5
このまとめたそれぞれの係数が $p$ の倍数となっていれば、任意の $x$ で $f(x)$ は $p$ の倍数と言える。
ただ、それ以外に答えが存在しない、という証明はよく理解できていない。
$p$ は素数なので $x \equiv 0 \mod{p}$ と表せる。
これを $f(x)$ に代入すると $f(0) = a_0 \mod{p}$ となるので、$a_0$ はそれ単体で $p$ の倍数となっている必要があることがわかる。
以上を総括すると、$f(x)$ が任意の整数 $x$ に対し $p$ で割り切れるための条件は、
$p \lt N+2$ である素数 $p$ については、実際に1つ1つ確かめる。たかだか $N \le 10^4$ なのでそれ以下の素数の数は知れている。
$p \ge N+2$ となったら、もう $f(x)$ の係数はまとめられない。よって $a_N～a_0$ 全てが $p$ の倍数である必要がある。 これは、全ての係数の最大公約数をとり、その素因数分解をすることで、求められる。
import sys
from fractions import gcd
def eratosthenes_generator():
yield 2
n = 3
h = {}
while True:
m = n
if n in h:
b = h[n]
del h[n]
else:
b = n
yield n
m += b << 1
while m in h:
m += b << 1
h[m] = b
n += 2
def prime(n):
ret = []
for i in eratosthenes_generator():
if n % i == 0:
ret.append(i)
while n % i == 0:
n = n // i
if n == 1 or i * i > n:
break
if n > 1:
ret.append(n)
return ret
def solve(n, aaa):
g = abs(aaa[-1])
for a in aaa[:-1]:
if a != 0:
g = gcd(g, abs(a))
ans = set(prime(g))
for p in eratosthenes_generator():
if p > n + 2:
break
if p in ans or aaa[0] % p != 0:
continue
q = p - 1
if all(sum(aaa[i::q]) % p == 0 for i in range(q)):
ans.add(p)
ans = sorted(ans)
return ans
n = int(input())
aaa = list(map(int, sys.stdin))
aaa.reverse()
print('\n'.join(map(str, solve(n, aaa))))
問題文がシンプル。こういうの好き（解けるとはいっていない）。
0は総和に影響しないので、後から挿入することで別に考えられる。「$1,2$ のみからなる長さ $1～N$ のそれぞれの個数」を求めればよい。
長さを $L$ に固定して、条件を満たす数列を考える。以下のいずれかの形となる。
1つめは、$L$ 個中に $r$ 個'2'があるとすると ${}_{L}C_{r}$ 通りの並べ方があるので、$r$ を総和が $X$ 以上にならない範囲で全部計算して足せばよい。
2つめはあるとしても1個固定。
3つめは少し観察が必要だが、左端から足していくとどこかで $X-1$ になるタイミングがある。すると次は'2'しか置けない。
? ? ? ... ? 2 ...
~~~~~~X-1~~~~~~
~~~~~~X+1~~~~~~~~~
すると、左端は'1'だったらアウトなので、2しか置けない
1 ? ? ... ? 2 ...
~~~~~~ X ~~~~~~ アウト
2 ? ? ... ? 2 ...
~~~~~~X-1~~~~~~ OK
するとさらに右はまた2しか置けない
2 ? ? ... ? 2 2 ...
~~~~~~X+1~~~~~~~~~
これを繰り返すと、両端は数列が規定の長さ L に達するまで2しか置けなくなる
両端には同数の2が並ぶことになる
2 2 2 ? ... ? 2 2 2
この時、右側の'2'の左端直前までの和が、X-1に等しくなる
|-k個-|
2 2 2 ? ... ? 2 2 2
~~~~~和 X-1~~~~~~~
部分列の和が $X$ にならないように作ろうとするとこの条件を満たすしかなく、 逆にこのように作ったものは「? ? ?」の部分がどうなっていようと必ず部分列の和が $X$ にならないことがわかる。
「$k=$ 両端にいくつ'2'が連続しているか」を全通り試す。
真ん中の「? ? ?」の部分は長さ $L-2k$、総和 $X-1-2k$ なので、'1'と'2'だけを置いて成立するか、する場合'2'は何個か、がわかる。二項係数で求められる。
さて、ここまでの1～3つめの数列の条件は、微妙に重複する場合があるので、注意して除く必要がある。
もう少しすっきりした分類の仕方があるかも知れないが、ひとまずこれで重複を除けた。
計算量は、二項係数の事前計算で $O(N^2)$、長さ $L$ を固定してその中で両端の'2'の個数を試すのに $O(N^2)$、あわせて $O(N^2)$ となる。