The moment I saw the problem, I wondered what K was for, but I didn't need it (laughs). The average value of 0 to N was the sum of 0 to N divided by N + 1. Since it is a thing, (0 + N) * (N + 1) ÷ 2 ÷ (N + 1), so N ÷ 2.
N, K = map(int, input().split())
print(N / 2)
I had a GCD version of SegmentTree, so it was an instant kill (laughs). Basically, it's a scale method. When GCD becomes 1, it's 1 no matter how far you go from there, so GCD (A i </ sub> >, A i + 1 </ sub>, ..., A j </ sub>) If it becomes 1 for the first time, A i </ sub> is the left end The number of subsequences whose GCD is 1 is N --j + 1. Next, we consider a subsequence with A i + 1 </ sub> at the left end, but of course the right end is j. This is the number above. Here, SegmentTree was used to calculate GCD (A i + 1 </ sub>, ..., A j </ sub>) at high speed. If j becomes N but GCD does not become 1, then GCD does not become 1 in the subsequence to the right of it, so the calculation can be stopped there.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func gcd(a, b int) int {
if a < b {
a, b = b, a
}
for b > 0 {
a, b = b, a%b
}
return a
}
type segmentTree struct {
data []int
offset int
}
func newSegmentTree(n int) segmentTree {
var result segmentTree
t := 1
for t < n {
t *= 2
}
result.offset = t - 1
result.data = make([]int, 2*t-1)
return result
}
func (st segmentTree) updateAll(a []int) {
for i, v := range a {
st.data[st.offset+i] = v
}
for i := st.offset - 1; i > -1; i-- {
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) update(index, value int) {
i := st.offset + index
st.data[i] = value
for i >= 1 {
i = (i - 1) / 2
st.data[i] = gcd(st.data[i*2+1], st.data[i*2+2])
}
}
func (st segmentTree) query(start, stop int) int {
result := 0
l := start + st.offset
r := stop + st.offset
for l < r {
if l&1 == 0 {
result = gcd(result, st.data[l])
}
if r&1 == 0 {
result = gcd(result, st.data[r-1])
}
l = l / 2
r = (r - 1) / 2
}
return result
}
func main() {
defer flush()
N := readInt()
A := make([]int, N)
for i := 0; i < N; i++ {
A[i] = readInt()
}
st := newSegmentTree(N)
st.updateAll(A)
result := 0
j := 1
for i := 0; i < N; i++ {
v := st.query(i, j)
for v != 1 && j < N {
v = gcd(v, A[j])
j++
}
if v != 1 {
break
}
result += N - j + 1
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
It goes in a clockwise vortex, but first think about what volume (I, J) is. It turns out that it is the minimum value of I, J, N -1 --I, N -1 --J. When the minimum value is l, the number of movements before entering the lth volume is the total number of movements N * N minus the number of movements after the lth volume (N − 2 * l) * (N − 2 * l). After that, you can answer by checking the movement taken by advancing only one roll and adding it to the number of movements until entering the lth roll.
Q = int(input())
for i in range(Q):
N, I, J = map(int, input().split())
l = min(I, J, N - 1 - I, N - 1 - J)
result = N * N - (N - 2 * l) * (N - 2 * l)
N, I, J = N - 2 * l, I - l, J - l
if I == 0:
result += J
elif J == N - 1:
result += N - 1 + I
elif I == N - 1:
result += 2 * (N - 1) + (N - 1) - J
elif J == 0:
result += 3 * (N - 1) + (N - 1) - I
print(result)
I wrote println (result) as print (result) and couldn't answer during the contest orz. When I wrote it in Python with the exact same algorithm, WA did not come out, but it was TLE, so I rewrote it in Go language. ing.
Every time I arrive at a gas station, I only do a DP with a pattern that puts fuel in and a pattern that does not put fuel in, so I think it's not particularly difficult. If the cost is high with the same amount of fuel, discard that pattern.
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
)
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
defer flush()
N := readInt()
V := readInt()
L := readInt()
cx := 0
d := map[int]int{}
d[V] = 0
for i := 0; i < N; i++ {
x := readInt()
v := readInt()
w := readInt()
nd := map[int]int{}
for k := range d {
t := k - (x - cx)
if t < 0 {
continue
}
_, ok := nd[t]
if !ok || nd[t] > d[k] {
nd[t] = d[k]
}
t = min(t+v, V)
_, ok = nd[t]
if !ok || nd[t] > d[k]+w {
nd[t] = d[k] + w
}
}
if len(nd) == 0 {
println(-1)
return
}
d = nd
cx = x
}
result := math.MaxInt64
for k := range d {
if k-(L-cx) >= 0 {
result = min(result, d[k])
}
}
println(result)
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
func readInts(n int) []int {
result := make([]int, n)
for i := 0; i < n; i++ {
result[i] = readInt()
}
return result
}
var stdoutWriter = bufio.NewWriter(os.Stdout)
func flush() {
stdoutWriter.Flush()
}
func printf(f string, args ...interface{}) (int, error) {
return fmt.Fprintf(stdoutWriter, f, args...)
}
func println(args ...interface{}) (int, error) {
return fmt.Fprintln(stdoutWriter, args...)
}
If the total number of painting methods using i types of paint is f (i), then f (i) = M </ sub> C i </ sub> * i N </ sup> --f (i -1). Also, f (0) = 0.
It took more than 5 hours to get to this, orz. ★ 2 or lie.
from sys import setrecursionlimit
setrecursionlimit(1000000)
N, M = map(int, input().split())
fac = [0] * (M + 1)
fac[0] = 1
for i in range(M):
fac[i + 1] = fac[i] * (i + 1) % 1000000007
def mcomb(n, k):
if n == 0 and k == 0:
return 1
if n < k or k < 0:
return 0
return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007
def f(i):
if i == 0:
return 0
return (mcomb(M, i) * pow(i, N, 1000000007) - f(i - 1)) % 1000000007
print(f(M))
Recommended Posts