原题链接
自己能想到的只有无脑暴力搜索,过了5个数据之后就超时了
import java.util.Scanner;
public class Main{
static int n,s,a,b,res;
static long[][] biao;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();s=sc.nextInt();a=sc.nextInt();b=0-sc.nextInt();biao=new long[n][n];
f(1,0);System.out.println(res);
//dp();
}
public static void f(int index,int num) {
if(index>=n) {
if((s-num)%n==0) {res++;}
return;
}
f(index+1,num+a*index);
f(index+1,num+b*index);
}
}
参照题解
import java.util.Scanner;
public class Main {
static int n,s,a,b,res;
static long[][] biao;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();s=sc.nextInt();a=sc.nextInt();b=0-sc.nextInt();biao=new long[n][n];
//f(1,0);System.out.println(res);
dp();
}
public static void dp() {
biao[0][0]=1;
for(int i=1;i<n;i++) {
for(int j=0;j<n;j++)
biao[i][j]=(biao[i-1][(((j-i*a)%n)+n)%n]+biao[i-1][(j-i*b)%n])%100000007;
}
System.out.println(biao[n-1][((s%n)+n)%n]);//s可能取负值
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla