HDU 6397 Character Encoding反発2018杭電多校第8場
Character Encoding
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 510 Accepted Submission(s): 194
Problem Description
In computer science, a character is a letter, a digit, a punctuation mark or some other similar symbol. Since computers can only process numbers, number codes are used to represent characters, which is known as character encoding. A character encoding system establishes a bijection between the elements of an alphabet of a certain size n and integers from 0 to n−1. Some well known character encoding systems include American Standard Code for Information Interchange (ASCII), which has an alphabet size 128, and the extended ASCII, which has an alphabet size 256. For example, in ASCII encoding system, the word wdy is encoded as [119, 100, 121], while jsw is encoded as [106, 115, 119]. It can be noticed that both 119+100+121=340 and 106+115+119=340, thus the sum of the encoded numbers of the two words are equal. In fact, there are in all 903 such words of length 3 in an encoding system of alphabet size 128 (in this example, ASCII). The problem is as follows: given an encoding system of alphabet size n where each character is encoded as a number between 0 and n−1 inclusive, how many different words of length m are there, such that the sum of the encoded numbers of all characters is equal to k? Since the answer may be large, you only need to output it modulo 998244353.
Input
The first line of input is a single integer T (1≤T≤400), the number of test cases. Each test case includes a line of three integers n,m,k (1≤n,m≤105,0≤k≤105), denoting the size of the alphabet of the encoding system, the length of the word, and the required sum of the encoded numbers of all characters, respectively. It is guaranteed that the sum of n, the sum of m and the sum of k don't exceed 5×106, respectively.
Output
For each test case, display the answer modulo 998244353 in a single line.
Sample Input
4
2 3 3
2 3 4
3 3 3
128 3 340
Sample Output
1
0
7
903
題意:明確な題意は,0からn−1の中からm個の数を選択し,kのシナリオ数と一致させることである.
構想:まず私たちはまずnを考慮しないで、まずm個の数を考慮して、構成のとkの組み合わせの方式を考慮して、私たちは仕切り板法の小球を置く問題と理解することができて、kをk個の1と見なしてそれからそれをm部に分けて、空にすることができて、このように私たちは仕切り板法の小球を置くことができて、答えはC(k+m-1、m-1)です;今私たちが求めているのはnの大きさにかかわらず、明らかにk>=nの時にある1部の中でnを超える組み合わせが現れて、私たちはどれかを見つけることができて、このm部は1部ごとにnを超える可能性があるので、C(m,i)、iはnを超える部数を表しています.これにより、部数が固定されている場合、どの部の中でnより大きい可能性があるかを見つけただけで、組み合わせは計算されていません.以前の仕切り板の小球の問題を考慮して、私たちは直接kをk-i*nとすればいいので、C(m,i)*C(k-i*n+m-1,m-1)i部がnを超える場合のすべての組合せを示し,その後,反発で解決できる.
コード:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 510 Accepted Submission(s): 194
Problem Description
In computer science, a character is a letter, a digit, a punctuation mark or some other similar symbol. Since computers can only process numbers, number codes are used to represent characters, which is known as character encoding. A character encoding system establishes a bijection between the elements of an alphabet of a certain size n and integers from 0 to n−1. Some well known character encoding systems include American Standard Code for Information Interchange (ASCII), which has an alphabet size 128, and the extended ASCII, which has an alphabet size 256. For example, in ASCII encoding system, the word wdy is encoded as [119, 100, 121], while jsw is encoded as [106, 115, 119]. It can be noticed that both 119+100+121=340 and 106+115+119=340, thus the sum of the encoded numbers of the two words are equal. In fact, there are in all 903 such words of length 3 in an encoding system of alphabet size 128 (in this example, ASCII). The problem is as follows: given an encoding system of alphabet size n where each character is encoded as a number between 0 and n−1 inclusive, how many different words of length m are there, such that the sum of the encoded numbers of all characters is equal to k? Since the answer may be large, you only need to output it modulo 998244353.
Input
The first line of input is a single integer T (1≤T≤400), the number of test cases. Each test case includes a line of three integers n,m,k (1≤n,m≤105,0≤k≤105), denoting the size of the alphabet of the encoding system, the length of the word, and the required sum of the encoded numbers of all characters, respectively. It is guaranteed that the sum of n, the sum of m and the sum of k don't exceed 5×106, respectively.
Output
For each test case, display the answer modulo 998244353 in a single line.
Sample Input
4
2 3 3
2 3 4
3 3 3
128 3 340
Sample Output
1
0
7
903
題意:明確な題意は,0からn−1の中からm個の数を選択し,kのシナリオ数と一致させることである.
構想:まず私たちはまずnを考慮しないで、まずm個の数を考慮して、構成のとkの組み合わせの方式を考慮して、私たちは仕切り板法の小球を置く問題と理解することができて、kをk個の1と見なしてそれからそれをm部に分けて、空にすることができて、このように私たちは仕切り板法の小球を置くことができて、答えはC(k+m-1、m-1)です;今私たちが求めているのはnの大きさにかかわらず、明らかにk>=nの時にある1部の中でnを超える組み合わせが現れて、私たちはどれかを見つけることができて、このm部は1部ごとにnを超える可能性があるので、C(m,i)、iはnを超える部数を表しています.これにより、部数が固定されている場合、どの部の中でnより大きい可能性があるかを見つけただけで、組み合わせは計算されていません.以前の仕切り板の小球の問題を考慮して、私たちは直接kをk-i*nとすればいいので、C(m,i)*C(k-i*n+m-1,m-1)i部がnを超える場合のすべての組合せを示し,その後,反発で解決できる.
コード:
#include
#include
#define MOD 998244353
const int maxed = 100000 + 10;
typedef unsigned long long ll;
ll A[maxed * 2];
int n, m, k;
int main()
{
ll slove(ll w, int x);
A[0] = 1;
for (int i = 1; i < 2 * maxed; ++i)
A[i] = A[i - 1] * i % MOD;
int N;
scanf("%d", &N);
while (N--) {
scanf("%d%d%d", &n, &m, &k);
ll answer = A[k + m - 1] * slove(A[m - 1] * A[k] % MOD, MOD - 2) % MOD;
//std::cout << "=====" << answer << std::endl;
for (int i = 1; ; ++i) {
if (1LL * i * n > k || i > m)
break;
if (i % 2)
answer = (answer - A[m] * slove(A[i] * A[m - i] % MOD, MOD - 2) % MOD * A[k - i * n + m - 1] % MOD * slove(A[m - 1] * A[k - i * n] % MOD, MOD - 2) % MOD + MOD) % MOD;
else
answer = (answer + A[m] * slove(A[i] * A[m - i] % MOD, MOD - 2) % MOD * A[k - i * n + m - 1] % MOD * slove(A[m - 1] * A[k - i * n] % MOD, MOD - 2) % MOD) % MOD;
}
printf("%lld
", answer);
}
return 0;
}
ll slove(ll w, int x)
{
ll a = 1;
while (x) {
if (x & 1)
a = a * w % MOD;
x >>= 1;
w = w * w % MOD;
}
return a;
}