hdu 6397 Character Encoding（逆元+容斥原理）

Problem DescriptionIn 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 r...

baby的我

177人浏览 · 2019-05-09 13:45:43

baby的我 · 2019-05-09 13:45:43 发布

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

Source

2018 Multi-University Training Contest 8

神一样的题目，神一样的大佬

这里讲的比较好： https://blog.csdn.net/gymgym1212/article/details/81708498

逆元运算：https://blog.csdn.net/qq_41431457/article/details/89813606

#include<bits/stdc++.h>
#define lom  long long 
#define M  200005
const int mod=998244353;
using namespace std;
lom inv[M],A[M];
lom quick(lom a,lom b,lom c)//快速幂取模 
{
	lom ans=1;
	a%=c;
	while(b)
	{
		if(b&1) ans=ans*a%c;
		a=a*a%c;	
		b>>=1;
	}
	return ans%c;
}
void getinv()
{
	inv[0]=quick(1,mod-2,mod);
	A[0]=1;
	for(int i=1;i<=M;i++)
	{
		A[i]=A[i-1]*i%mod;//i!
		inv[i]=quick(A[i],mod-2,mod);//i! 的逆元 
	}
}
lom C(lom a,lom b) 
{
	if(b>a) return 0;
	return A[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
	getinv();
	int t;
	cin>>t;
	while(t--)
	{
		lom n,m,k;
		cin>>n>>m>>k;
		if(k==0)
			cout<<'1'<<endl;
		else if(k>m*(n-1))
			cout<<'0'<<endl;
		else if(k<n)
			cout<<C(m+k-1,k)<<endl;
		else 
		{
			lom ans=C(m+k-1,m-1);
			int flag=-1;
			for(int i=1; i<=m; i++)
			{
				ans+=flag*C(m,i)*C(m+k-i*n-1,m-1)%mod;
				ans=(ans%mod+mod)%mod;
				flag=-1*flag;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

操作系统大会&openEuler Summit 2024参会指南，请查收！