Submission #153196

---

Source Code Expand

import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		new Main().run();
	}

	void run()
	{
		Scanner cin = new Scanner(System.in);
		int N = cin.nextInt();
		int M = cin.nextInt();
		int K = cin.nextInt();
		int[] D = new int[N - 1];

		for(int i=0;i<N-1;i++){
			D[i] = cin.nextInt();
		}
		if(N>12) return;

		//2つの街の間の距離を計算する
		int[][] dist = new int[N][N];
		for(int i=0;i<N;i++){
			int nowdist = 0;
			for(int j=i+1;j<N;j++){
				nowdist += D[j-1];
				nowdist %= M;
				dist[i][j] = dist[j][i] = nowdist;
			}
		}
		
		//配列の初期化
		int mod = 1000000007;
		long[][][] dp = new long[1<<N][N][M];
		for(int i=0;i<N;i++){
			dp[1<<i][i][0] = 1;
		}
		
		
		for(int i=0;i<(1<<N);i++){
			for(int j=0;j<N;j++){
				for(int k=0;k<M;k++){
					if(dp[i][j][k]==0) continue;
					//次の街を全通り調べる
					for(int l=0;l<N;l++){
						if((i>>l) % 2 == 1) continue;
						int nexti = i | (1 << l);
						int nextk = (k + dist[j][l]) % M;
						dp[nexti][l][nextk] += dp[i][j][k];
						dp[nexti][l][nextk] %= mod;
					}
				}
			}
		}
		
		//K個の街を訪れて、余りが0のパターンを全列挙
		long ret = 0;
		for(int i=0;i<(1<<N);i++){
			if(Integer.bitCount(i) != K) continue;
			for(int j=0;j<N;j++){
				ret += dp[i][j][0];
				ret %= mod;
			}
		}
		System.out.println(ret);
	}
}

Submission Info

Judge Result