Resource limit time limit: 1.0 s
Memory limit: 256.0 MB
Problem description
Look at this sequence:
1 3 0 1-2-1 2...
After the sequence of a is always better than before a 2 or 3, less
Small is curious about this series, he wants to know the length for n and s before and after a is always better than a increase or reduce b integer sequence may be what kind of?
Input format
The first line of the input contains four integer n a, b, s meaning as previously said,
The output format
Output a line contains an integer that satisfy the conditions on the number of solutions, as a result of this number is very big, please output plan number divided by the remainder of 100000007,
The sample input
10 2, 3, 4
Sample output
2
The sample description
The two series are respectively 4 1 2 3 and 7 4 1 or 2, data size and conventions
About 10% of the data, 1 & lt;=n<5, 0=& lt;=s<=5, 1 & lt;=a, b<=5;
About 30% of the data, 1 & lt;=n<30, 0=& lt;=s<=30, 1 & lt;=a, b<=30;
About 50% of the data, 1 & lt;=n<=50, 0 & lt;=s<=50, 1 & lt;=a, b<=50;
About 70% of the data, 1 & lt;=n<=100, 0 & lt;=s<=500, 1 & lt;=a, b<=50;
About 100% of the data, 1 & lt;=n<=1000-1000000000 & lt;=s<=1000000000, 1 & lt;=a, b<=1000000,
I wrote the program is:
# using the python language features, glue cross-platform use Java, optimize
# to use this method to add a jpype extensions library
In the Java code for:
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
}
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 - * a + l (n * (n - 1)/2 - l) * b;
If % (s1==0 1000) {
Ans +=dp [l] (int);
Ans %=mod; }}
return ans; }}
In the python code:
The import jpype n=list (map (int, input (). The split ()))
Jpype. StartJVM (r "C: \ ProgramFiles \ Java \ jdk1.8.0 _111 \ jre \ bin \ server \ JVM DLL", "- ea", "- Djava. Class. Path=% s" % r "h D: \ \ hr. Jar") # open the JVM
Javaclass=jpype. JClass (" com. Java. Python. JavaPython ") # loading Java classes (parameter is a Java class name) print (javaclass. Main (n [0], n [1], n [2], n [3])) # call a Java method (static method can directly use the name of the class calls)
Jpype. ShutdownJVM ()
Print (time. Time () - start)
Time performance of this method is more than four seconds, excuse me, is there any other method, can be in 1 seconds can achieve
, every brother please grant instruction!
CodePudding user response:
The import itertools
Import a datetime
Now=datetime. Datetime. Now ()
Print (now)
# s=input (' n s a, b)
S='10 2, 3, 4'
N, s, a, b=(int (x) for x in the list (s.s plit (" ")))
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) : # permutation and combination
# print (', '. Join (STR) (I). The replace (', ', '), end=' ')
Templist=[]
Templist. Append (a list (I))
Templist. Append (sum ([a * b for a, b in zip (cc, the list (I)))))
Total. Append (templist)
Print (total)
Result=[]
For I in range (startmin startmax + 1) :
For k in total:
If the int [1]) (k + n * I==s:
Templist=[]
Templist. Append (I)
Templist. Append (k)
Result. Append (templist)
Print (len (result), the result)
Print (datetime. Datetime. Now ())
CodePudding user response: