題目：波動數列
資源限制時間限制：1.0s
記憶體限制：256.0MB
問題描述
觀察這個數列：
1 3 0 2 -1 1 -2 ...
這個數列中后一項總是比前一項增加2或者減少3。
棟棟對這種數列很好奇，他想知道長度為 n 和為 s 而且后一項總是比前一項增加a或者減少b的整數數列可能有多少種呢？
輸入格式
輸入的第一行包含四個整數 n s a b，含義如前面說述。
輸出格式
輸出一行，包含一個整數，表示滿足條件的方案數。由于這個數很大，請輸出方案數除以100000007的余數。
樣例輸入
4 10 2 3
樣例輸出
2
樣例說明
這兩個數列分別是2 4 1 3和7 4 1 -2。資料規模和約定
對于10%的資料，1<=n<=5，0<=s<=5，1<=a,b<=5；
對于30%的資料，1<=n<=30，0<=s<=30，1<=a,b<=30；
對于50%的資料，1<=n<=50，0<=s<=50，1<=a,b<=50；
對于70%的資料，1<=n<=100，0<=s<=500，1<=a, b<=50；
對于100%的資料，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a, b<=1,000,000。
我寫的程式是：
#利用python膠水語言的特性，跨平臺使用java，進行優化
#使用該方法要加一個jpype的擴展庫
Java里的代碼為：
package com.java.python;
public class JavaPython {
public static long main(int n,int s,int a,int b) {
int i,j,k,t=n*(n-1)/2,mod=100000007;
long ans=0,l,s1;
int[] dp=new int[t+1]；
for(k=0;k<t+1;k++){
dp[k]=0;
}
dp[0]=1;
for(i=1;i<1000;++i){
for(j=i*(i+1)/2;j>=i;--j){
dp[j]=(dp[j]+dp[j-i])%mod;
} }
for(l=0;l<(t+1);++l){
s1=s-l*a+(n*(n-1)/2-l)*b;
if(s1%1000==0){
ans+=dp[(int) l];
ans%=mod; } }
return ans; }}
python里的代碼：
import jpype n=list(map(int,input().split()))
jpype.startJVM(r"C:\ProgramFiles\Java\jdk1.8.0_111\jre\bin\server\jvm.dll","-ea","-Djava.class.path=%s" % r"D:\h\hr.jar")#打開jvm
javaclass=jpype.JClass("com.java.python.JavaPython")#加載java類（引數是java的長類名）print(javaclass.main(n[0],n[1],n[2],n[3]))#呼叫java方法（靜態方法可直接用類名呼叫）
jpype.shutdownJVM()
print(time.time()-start)
這個方法的時間性能是四秒多，請問各位大佬還有沒有其他的方法，能夠在1秒內就能實作
請各位大佬賜教！
uj5u.com熱心網友回復：
import itertools
import datetime
now=datetime.datetime.now()
print(now)
#s=input ('n s a b ')
s='4 10 2 3'
n,s,a,b=(int(x) for x in list(s.split(" ")))
print(n,s,a,b)
startmin=s/n-(n-1)*a/2
startmax=s/n+(n-1)*b/2
startmin,startmax=int(startmin),int(startmax)
total=[]
cc=list(_ for _ in range(n-1,0,-1))
print(cc)
for i in itertools.product([a,-b],repeat=3): #排列組合
#print(','.join(str(i)).replace(',',''),end='')
templist=[]
templist.append(list(i))
templist.append(sum([a*b for a,b in zip(cc,list(i))]))
total.append(templist)
print(total)
result=[]
for i in range(startmin,startmax+1):
for k in total:
if int(k[-1])+n*i==s:
templist=[]
templist.append(i)
templist.append(k)
result.append(templist)
print(len(result),result)
print(datetime.datetime.now())
uj5u.com熱心網友回復：
哥，你這個資料小的時候是可以的，但是用到這個就不行啦（1000,134182393,234891,410392）
uj5u.com熱心網友回復：
還得滿足這個資料：1000,134182393,234891,410392
時間上的性能小于1秒，而且記憶體也不能太大
uj5u.com熱心網友回復：
https://blog.csdn.net/qq_32792879/article/details/57122975還得是C吧，
uj5u.com熱心網友回復：
所以我才跨平臺使用了JAVA，但是也換得需要四秒
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/54193.html