from collections import defaultdict def num_dc(A): res = 0 n = N dp = [defaultdict(int) for _ in range(n)] for i in range(1, n): for j in range(i): diff = A[i] - A[j] dp[i][diff] += 1 if diff in dp[j]: dp[i][diff] += dp[j][diff] res += dp[j][diff] return res N = int(input()) A = list(map(int, input().split())) print((num_dc(A)+int(N*(N+1)/2))%9901)
解题思路:就是找到3个和3个以上的等差数列+2个/1个,
以 A = [1,4,2,3,7]举例,After iteration 1,这里1为i的值
Initial state:
i | dp
--------------
0 | defaultdict(<class 'int'>, {})
1 | defaultdict(<class 'int'>, {})
2 | defaultdict(<class 'int'>, {})
3 | defaultdict(<class 'int'>, {})
4 | defaultdict(<class 'int'>, {})
res = 0
After iteration 1:
i | dp
--------------
0 | defaultdict(<class 'int'>, {})
1 | defaultdict(<class 'int'>, {3: 1})
2 | defaultdict(<class 'int'>, {})
3 | defaultdict(<class 'int'>, {})
4 | defaultdict(<class 'int'>, {})
res = 0
After iteration 2:
i | dp
--------------
0 | defaultdict(<class 'int'>, {})
1 | defaultdict(<class 'int'>, {3: 1})
2 | defaultdict(<class 'int'>, {1: 1, -2: 1})
3 | defaultdict(<class 'int'>, {})
4 | defaultdict(<class 'int'>, {})
res = 0
After iteration 3:
i | dp
--------------
0 | defaultdict(<class 'int'>, {})
1 | defaultdict(<class 'int'>, {3: 1})
2 | defaultdict(<class 'int'>, {1: 1, -2: 1})
3 | defaultdict(<class 'int'>, {2: 1, -1: 1, 1: 2})
4 | defaultdict(<class 'int'>, {})
res = 1
After iteration 4:
i | dp
--------------
0 | defaultdict(<class 'int'>, {})
1 | defaultdict(<class 'int'>, {3: 1})
2 | defaultdict(<class 'int'>, {1: 1, -2: 1})
3 | defaultdict(<class 'int'>, {2: 1, -1: 1, 1: 2})
4 | defaultdict(<class 'int'>, {6: 1, 3: 2, 5: 1, 4: 1})
res = 2
计算差值并记录出现次数:
diff = 1 出现了 2 次,此时 res 加 1。
diff = 3 出现了 2 次,此时 res 加 1。
同理出现了3次,res+2
最终返回 res 的值为 2。
0.0分
1 人评分