Submission #58061


Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N, K;
	static int less;
	static String s;
	static int MOD = 1000000007;

	public static void main(String[] args) {
		N = sc.nextInt();
		K = sc.nextInt();
		s = sc.next();
		K -= s.length();
		less = s.charAt(0) - 'a';
		for (int i = 1; i < s.length(); ++i) {
			if (s.charAt(i) < s.charAt(0)) --less;
		}
		int left = N;
		for (int i = 0; i < N; ++i) {
			if (i + 'a' < s.charAt(0) || s.contains("" + (char) (i + 'a'))) {
				--left;
			}
		}
		long ans = 0;
		for (int i = 0; i <= N - s.length(); ++i) {
			ans += solve(i);
		}
		for (int i = 0; i < left; ++i) {
			ans *= (i + 1);
			ans %= MOD;
		}
		for (int i = 0; i < less; ++i) {
			ans *= (i + 1);
			ans %= MOD;
		}
		System.out.println(ans % MOD);
	}

	static long solve(int pos) {
		int rem = K;
		for (int i = 1; i < s.length(); ++i) {
			if (s.charAt(i) < s.charAt(0)) {
				rem -= N - (pos + i);
			}
		}
		if (rem < 0) return 0;
		long[][] dp = new long[rem + 1][less + 1];
		dp[0][0] = 1;
		for (int i = 0; i < N; ++i) {
			if (pos <= i && i < pos + s.length()) continue;
			for (int j = rem - (N - i); j >= 0; --j) {
				for (int k = less - 1; k >= 0; --k) {
					dp[j + N - i][k + 1] += dp[j][k];
					if (dp[j + N - i][k + 1] >= MOD) dp[j + N - i][k + 1] -= MOD;
				}
			}
		}
		long ans = dp[rem][less];
		return ans;
	}
}

Submission Info

Submission Time
Task G - k番目の文字列
User tomerun
Language Java (OpenJDK 1.7.0)
Score 200
Code Size 1489 Byte
Status AC
Exec Time 462 ms
Memory 23284 KB

Judge Result

Set Name Set 01 Set 02
Score / Max Score 50 / 50 150 / 150
Status
AC × 86
AC × 122
Set Name Test Cases
Set 01 020_10_02.txt, 020_10_04.txt, 020_10_05.txt, 020_10_06.txt, 020_10_07.txt, 020_10_08.txt, 020_10_10.txt, 020_20_01.txt, 020_20_02.txt, 020_20_03.txt, 020_20_05.txt, 020_20_06.txt, 020_20_07.txt, 020_20_08.txt, 020_20_10.txt, 020_20_11.txt, 020_20_12.txt, 020_20_14.txt, 020_20_16.txt, 020_20_19.txt, 020_20_20.txt, 020_20_21.txt, 020_20_23.txt, 020_20_24.txt, 020_20_26.txt, 020_20_28.txt, 020_30_01.txt, 020_40_01.txt, 020_40_02.txt, 020_40_03.txt, 020_40_04.txt, 020_40_05.txt, 020_40_06.txt, 020_40_07.txt, 020_40_08.txt, 020_40_09.txt, 020_40_10.txt, 020_40_11.txt, 020_40_12.txt, 020_40_13.txt, 020_40_14.txt, 020_40_15.txt, 020_40_16.txt, 020_40_17.txt, 020_40_18.txt, 020_40_19.txt, 020_40_20.txt, 020_60_01.txt, 020_60_03.txt, 020_60_05.txt, 020_60_06.txt, 020_60_07.txt, 020_60_08.txt, 020_60_09.txt, 020_70_01.txt, 020_70_02.txt, 020_70_05.txt, 020_70_06.txt, 020_70_11.txt, 020_70_14.txt, 020_70_16.txt, 020_70_20.txt, 020_70_21.txt, 020_70_26.txt, 020_70_28.txt, 020_80_01.txt, 020_90_01.txt, 020_90_02.txt, 020_90_03.txt, 020_90_04.txt, 020_90_05.txt, 020_90_06.txt, 020_90_07.txt, 020_90_08.txt, 020_90_09.txt, 020_90_10.txt, 020_90_11.txt, 020_90_12.txt, 020_90_13.txt, 020_90_14.txt, 020_90_15.txt, 020_90_16.txt, 020_90_17.txt, 020_90_18.txt, 020_90_19.txt, 020_90_20.txt
Set 02 020_10_02.txt, 020_10_04.txt, 020_10_05.txt, 020_10_06.txt, 020_10_07.txt, 020_10_08.txt, 020_10_10.txt, 020_20_01.txt, 020_20_02.txt, 020_20_03.txt, 020_20_05.txt, 020_20_06.txt, 020_20_07.txt, 020_20_08.txt, 020_20_10.txt, 020_20_11.txt, 020_20_12.txt, 020_20_14.txt, 020_20_16.txt, 020_20_19.txt, 020_20_20.txt, 020_20_21.txt, 020_20_23.txt, 020_20_24.txt, 020_20_26.txt, 020_20_28.txt, 020_30_01.txt, 020_40_01.txt, 020_40_02.txt, 020_40_03.txt, 020_40_04.txt, 020_40_05.txt, 020_40_06.txt, 020_40_07.txt, 020_40_08.txt, 020_40_09.txt, 020_40_10.txt, 020_40_11.txt, 020_40_12.txt, 020_40_13.txt, 020_40_14.txt, 020_40_15.txt, 020_40_16.txt, 020_40_17.txt, 020_40_18.txt, 020_40_19.txt, 020_40_20.txt, 020_60_01.txt, 020_60_03.txt, 020_60_05.txt, 020_60_06.txt, 020_60_07.txt, 020_60_08.txt, 020_60_09.txt, 020_70_01.txt, 020_70_02.txt, 020_70_05.txt, 020_70_06.txt, 020_70_11.txt, 020_70_14.txt, 020_70_16.txt, 020_70_20.txt, 020_70_21.txt, 020_70_26.txt, 020_70_28.txt, 020_80_01.txt, 020_90_01.txt, 020_90_02.txt, 020_90_03.txt, 020_90_04.txt, 020_90_05.txt, 020_90_06.txt, 020_90_07.txt, 020_90_08.txt, 020_90_09.txt, 020_90_10.txt, 020_90_11.txt, 020_90_12.txt, 020_90_13.txt, 020_90_14.txt, 020_90_15.txt, 020_90_16.txt, 020_90_17.txt, 020_90_18.txt, 020_90_19.txt, 020_90_20.txt, 100_10_01.txt, 100_10_03.txt, 100_10_09.txt, 100_20_04.txt, 100_20_09.txt, 100_20_13.txt, 100_20_15.txt, 100_20_17.txt, 100_20_18.txt, 100_20_22.txt, 100_20_25.txt, 100_20_27.txt, 100_20_29.txt, 100_20_30.txt, 100_60_02.txt, 100_60_04.txt, 100_60_10.txt, 100_70_03.txt, 100_70_04.txt, 100_70_07.txt, 100_70_08.txt, 100_70_09.txt, 100_70_10.txt, 100_70_12.txt, 100_70_13.txt, 100_70_15.txt, 100_70_17.txt, 100_70_18.txt, 100_70_19.txt, 100_70_22.txt, 100_70_23.txt, 100_70_24.txt, 100_70_25.txt, 100_70_27.txt, 100_70_29.txt, 100_70_30.txt
Case Name Status Exec Time Memory
020_10_02.txt AC 416 ms 19848 KB
020_10_04.txt AC 418 ms 19912 KB
020_10_05.txt AC 418 ms 19860 KB
020_10_06.txt AC 418 ms 19924 KB
020_10_07.txt AC 422 ms 19796 KB
020_10_08.txt AC 411 ms 19884 KB
020_10_10.txt AC 419 ms 19856 KB
020_20_01.txt AC 421 ms 19912 KB
020_20_02.txt AC 422 ms 19868 KB
020_20_03.txt AC 417 ms 19856 KB
020_20_05.txt AC 420 ms 19860 KB
020_20_06.txt AC 420 ms 19736 KB
020_20_07.txt AC 430 ms 19844 KB
020_20_08.txt AC 405 ms 19748 KB
020_20_10.txt AC 436 ms 19860 KB
020_20_11.txt AC 419 ms 19884 KB
020_20_12.txt AC 419 ms 19792 KB
020_20_14.txt AC 414 ms 19916 KB
020_20_16.txt AC 418 ms 19720 KB
020_20_19.txt AC 423 ms 19788 KB
020_20_20.txt AC 421 ms 19864 KB
020_20_21.txt AC 418 ms 19868 KB
020_20_23.txt AC 414 ms 19728 KB
020_20_24.txt AC 422 ms 19796 KB
020_20_26.txt AC 419 ms 19828 KB
020_20_28.txt AC 415 ms 19844 KB
020_30_01.txt AC 419 ms 19876 KB
020_40_01.txt AC 414 ms 19856 KB
020_40_02.txt AC 425 ms 19724 KB
020_40_03.txt AC 428 ms 19784 KB
020_40_04.txt AC 434 ms 19732 KB
020_40_05.txt AC 440 ms 19852 KB
020_40_06.txt AC 450 ms 19756 KB
020_40_07.txt AC 417 ms 19792 KB
020_40_08.txt AC 413 ms 19856 KB
020_40_09.txt AC 411 ms 19860 KB
020_40_10.txt AC 418 ms 19876 KB
020_40_11.txt AC 429 ms 19856 KB
020_40_12.txt AC 418 ms 19880 KB
020_40_13.txt AC 414 ms 19720 KB
020_40_14.txt AC 417 ms 19920 KB
020_40_15.txt AC 416 ms 19848 KB
020_40_16.txt AC 409 ms 19732 KB
020_40_17.txt AC 412 ms 19784 KB
020_40_18.txt AC 427 ms 19856 KB
020_40_19.txt AC 416 ms 19748 KB
020_40_20.txt AC 413 ms 19788 KB
020_60_01.txt AC 418 ms 19872 KB
020_60_03.txt AC 418 ms 19728 KB
020_60_05.txt AC 450 ms 19864 KB
020_60_06.txt AC 417 ms 19724 KB
020_60_07.txt AC 407 ms 19852 KB
020_60_08.txt AC 432 ms 19880 KB
020_60_09.txt AC 427 ms 19816 KB
020_70_01.txt AC 414 ms 19916 KB
020_70_02.txt AC 419 ms 19784 KB
020_70_05.txt AC 421 ms 19864 KB
020_70_06.txt AC 417 ms 19852 KB
020_70_11.txt AC 424 ms 19796 KB
020_70_14.txt AC 418 ms 19880 KB
020_70_16.txt AC 418 ms 19872 KB
020_70_20.txt AC 427 ms 19872 KB
020_70_21.txt AC 416 ms 19788 KB
020_70_26.txt AC 434 ms 19748 KB
020_70_28.txt AC 439 ms 19744 KB
020_80_01.txt AC 430 ms 19800 KB
020_90_01.txt AC 421 ms 19780 KB
020_90_02.txt AC 422 ms 19852 KB
020_90_03.txt AC 411 ms 19844 KB
020_90_04.txt AC 420 ms 19864 KB
020_90_05.txt AC 416 ms 19916 KB
020_90_06.txt AC 433 ms 19876 KB
020_90_07.txt AC 433 ms 19792 KB
020_90_08.txt AC 430 ms 19724 KB
020_90_09.txt AC 426 ms 19796 KB
020_90_10.txt AC 413 ms 19916 KB
020_90_11.txt AC 427 ms 19844 KB
020_90_12.txt AC 418 ms 19752 KB
020_90_13.txt AC 414 ms 19856 KB
020_90_14.txt AC 422 ms 19876 KB
020_90_15.txt AC 413 ms 19848 KB
020_90_16.txt AC 412 ms 19868 KB
020_90_17.txt AC 417 ms 19784 KB
020_90_18.txt AC 414 ms 19856 KB
020_90_19.txt AC 409 ms 19880 KB
020_90_20.txt AC 413 ms 19792 KB
100_10_01.txt AC 415 ms 19876 KB
100_10_03.txt AC 413 ms 19784 KB
100_10_09.txt AC 413 ms 19856 KB
100_20_04.txt AC 428 ms 19908 KB
100_20_09.txt AC 416 ms 19860 KB
100_20_13.txt AC 412 ms 19788 KB
100_20_15.txt AC 418 ms 19860 KB
100_20_17.txt AC 420 ms 19856 KB
100_20_18.txt AC 416 ms 19796 KB
100_20_22.txt AC 423 ms 19856 KB
100_20_25.txt AC 434 ms 19808 KB
100_20_27.txt AC 410 ms 19908 KB
100_20_29.txt AC 417 ms 19876 KB
100_20_30.txt AC 420 ms 19880 KB
100_60_02.txt AC 431 ms 20236 KB
100_60_04.txt AC 420 ms 19888 KB
100_60_10.txt AC 432 ms 19788 KB
100_70_03.txt AC 455 ms 22168 KB
100_70_04.txt AC 407 ms 19872 KB
100_70_07.txt AC 454 ms 22280 KB
100_70_08.txt AC 449 ms 22088 KB
100_70_09.txt AC 462 ms 22040 KB
100_70_10.txt AC 429 ms 20692 KB
100_70_12.txt AC 429 ms 20112 KB
100_70_13.txt AC 442 ms 21256 KB
100_70_15.txt AC 457 ms 23284 KB
100_70_17.txt AC 419 ms 19900 KB
100_70_18.txt AC 413 ms 19780 KB
100_70_19.txt AC 438 ms 20808 KB
100_70_22.txt AC 421 ms 19848 KB
100_70_23.txt AC 437 ms 20168 KB
100_70_24.txt AC 423 ms 19844 KB
100_70_25.txt AC 449 ms 22564 KB
100_70_27.txt AC 444 ms 20244 KB
100_70_29.txt AC 446 ms 22104 KB
100_70_30.txt AC 444 ms 21252 KB
sample1.txt AC 415 ms 19848 KB
sample2.txt AC 420 ms 19880 KB
sample3.txt AC 428 ms 19884 KB
sample4.txt AC 457 ms 22728 KB