介绍
这个平台貌似对所有语言都采用同一个Time Limit,那python在同等时间复杂度下要比C慢好几倍,难度也就翻了好几倍,我感觉我已经优化的不能再优化了,还是TLE。那就简单写写思路吧,看看有没有佬能帮忙再优化一下。
思路
从例子入手分析规律,例子的两个答案可以用以下的方式表示:
+2 +2-3 +2-3+2 +2*4 = 10
-3 -3-3 -3-3-3 +7*4 = 10
-
其中,等号左边前
n-1
项为第1~n-1
个数相对于第0
个数的偏移,第n
项为第0
个数乘以n
;等号右边为s
。 -
可以发现,有一个
a
或-b
用到了n-1
次,有一个a
或-b
用到了n-2
次,… ,有一个a
或-b
用到了1
次。 -
由此可以总结规律,并将问题转化为:我们需要找到有多少个方案
D={d_n-1, d_n-2, ... ,d_1}
使得对于(n-1)*d_n-1 + (n-2)*d_n-2 + ... + 1*d_1 + x*n = s
存在一个整数x
使等号成立,其中d_1 ~ d_n-1
都可以取a
或者-b
。 -
进一步转化,也就是:在所有可能的方案
D
中找到满足{s - [(n-1)*d_n-1 + (n-2)*d_n-2 + ... + 1*d_1)]} % n == 0
的方案数
python代码
def get_amount_a(n): #统计在所有方案中,偏移量a用到的总次数的所有可能情况 及 该次数对应的方案数
amount_a = {'0':1} #该字典的key和value分别对应于上述两项
for i in range(1, n): #对于出现次数为1~n的各项,都有取a或者取-b两种情况
new_amount_a = amount_a.copy() #amount_a包含了该次循环不取a的情况
for key, value in amount_a.items(): #加上该次循环取a的情况
new_amount_a[str(int(key) + i)] = new_amount_a.get(str(int(key) + i), 0) + value
amount_a = new_amount_a.copy()
return amount_a
n, s, a, b = map(int, input().split())
res = 0
amount_all = sum([i for i in range(n)]) #偏移量的总出现次数为1+2+...+n-1
amount_a = get_amount_a(n) #amount_b = amount_all - amount_a
for key, value in amount_a.items():
if (s - (a*int(key) - b*(amount_all-int(key)))) % n == 0:
res = (res+value) % 100000007
print(res)