URAL 1036. Lucky Tickets(dp+大数)

发布时间：2020-12-14 03:34:31 所属栏目：大数据来源：网络整理

导读：题目很水，就是得用到大数，用Java过的

题目很水，就是得用到大数，用Java过的啊、、

就是给你n，s。判断前面n个数和后面n个数的和为s/2的情况有多少种。注意s为奇数输出0.

1036. Lucky Tickets

Time limit: 2.0 second
Memory limit: 64 MB

You are given a number 1 ≤? N?≤ 50. Every ticket has its 2 N-digit number. We call a ticket lucky,if the sum of its first? N?digits is equal to the sum of its last? N?digits. You are also given the sum of ALL digits in the number. Your task is to count an amount of lucky numbers,having the specified sum of ALL digits.

Input

Two space-separated numbers:? N?and? S. Here? S?is the sum of all digits. Assume that 0 ≤? S?≤ 1000.

Output

The amount of lucky tickets.

Sample

input	output
2 2	4

Hint

The tickets are 0101,0110,1001,1010 in the example above

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String agrs[]) {
		Scanner cin = new Scanner(System.in);
		BigInteger dp[][] = new BigInteger[101][1001];
		int i,j,k;
		for (i = 0; i <= 100; i++) {
			for (j = 0; j <= 1000; j++)
				dp[i][j] = BigInteger.valueOf(0);
		}
		dp[0][0] = BigInteger.valueOf(1);
		for (i = 1; i <= 51; i++) {
			for (j = 0; j <= i * 10; j++) {
				for (k = 0; k <= 9; k++) {
					if (dp[i - 1][j].compareTo(BigInteger.valueOf(0)) != 0) {
						dp[i][j + k] = dp[i][j + k].add(dp[i - 1][j]);
					}
				}
			}
		}
		int n,s;
		while (cin.hasNext()) {
			n = cin.nextInt();
			s = cin.nextInt();
			if (s % 2 == 1)
				System.out.println("0");
			else
				System.out.println(dp[n][s / 2].multiply(dp[n][s / 2]));
		}
	}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!