HDU 6397 组合数学+容斥 母函数
Character Encoding
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1473 Accepted Submission(s): 546
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.
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.
容斥写法
x1+x2+...+xm = k (xi>=0) 共有C(k+m-1,m-1) 种 插板法
如果有c个违反条件 把每一个违反条件的x减去n
x1'+x2'+x3'+x4'+x5'+...+xn'= k-c*n xi>=0 共有 C(k-c*n+m-1,m-1)种
容斥系数 变量选法
ans = (-1)^c * C(m,c) * C(k-cn+m-1,m-1)
母函数写法
1+x+x^2+...+x^(n-1)=(1-x^n)/(1-x)
(1+x+x^2+...+x^(n-1))^m
=(1-x^n)^m/(1-x)^m
=(1-x^n)^m*(1-x)^(-m)
=(1-x^n)^m*(sum_ (x^i)*C(m+i-1,m-1)) //上篇博客说的核武器。。。。
ans=x^k 的系数
左边二项式展开 按照每个i 右边应该有k-ni
ans= sum (-1)^i*C(m,i)*C(m+k-n*I-1,m-1)
左边 x^n*i 右边x^(k-n*i)
系数(-1)^i*C(m,i) 系数C(m+k-n*I-1,m-1)
AC代码
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n");
#define debug(a,b) cout<<a<<" "<<b<<" "<<endl;
using namespace std;
const int maxn= 3e5+;
const int inf = 0x3f3f3f3f,mod=;
typedef long long ll;
ll fac[maxn],inv[maxn];
void init()
{
fac[]=fac[]=;
inv[]=inv[]=;
for(ll i=;i<maxn;i++)
{
fac[i]=fac[i-]*i%mod;
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
for(ll i=;i<maxn;i++)
inv[i]=inv[i-]*inv[i]%mod;
}
ll C(ll x,ll y)
{
if(y>x) return ;
if(y==||x==) return ;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
ll n,m,k,t;
init();
cin>>t;
while(t--)
{
cin>>n>>m>>k;
if(k==)
{
cout<<<<endl;
continue;
}
else if((n-)*m<k)
{
cout<<<<endl;
continue;
}
int c=min(k/n,m);
ll ans=;
for(int i=;i<=c;i++)
{
if(i%==)
ans=(ans+C(m,i)*C(k-i*n+m-,m-)%mod)%mod;
else
ans=(ans-C(m,i)*C(k-i*n+m-,m-)%mod+mod)%mod;
}
cout<<ans<<endl;
}
}
最新文章
- pullToRefreshListView的简单使用
- Android 动画分类
- BZOJ3160: 万径人踪灭
- web_reg_find()函数的使用
- WinStore开发知识导航集锦
- Linux建立软连接
- 学习MVC框架的步骤
- iOS block简单传值
- map,area标签
- $POST 、$HTTP_RAW_POST_DATA、php://input三者之间的差别
- 使用JavaScript检测浏览器
- python 压缩 解压缩 文件
- js基础---cookie存储
- 【Spring】面向切面之AOP
- c++ stl sort 自定义排序函数cmp要遵循 strict weak ordering
- gflags 学习
- 自然语言处理的CNN模型中几种常见的池化方法
- 开源网络库ACE、Boost的ASIO、libevent、libev、ZeroMQ
- 【转】JavaScript 事件顺序:冒泡和捕获
- jenkins webhook 配置
热门文章
- 激活eclipse自动提示功能
- 生产线上的Nginx如何添加未编译安装模块
- 获取父页面的dom元素
- ArrayList Vector LinkedList分析
- this.$emit(&#39;on-select-change&#39; emit里面不能写大写字母
- Android Studio集成crashlytics后无法编译的问题
- 暑假集训 || 状压DP
- Linux环境下挂载SD卡的教程
- typedef重复定义 和 error: ‘long long long’ is too long for GCC
- 洛谷 1067 NOIP2009 普及组 多项式输出