题目描述

求关于x的方程:x1+x2+……xk=n的非负整数解的个数。

输入格式

仅一行,包含两个正整数n,k。

输出格式

一个整数,表示方程不同解的个数,这个数可能很大,你只需输出mod 20080814 的结果。

输入样例

1 1

输出样例

1
  提示
  数据范围
  对于50%的数据,n,k<=300
  对于80%的数据,n,k<=1000
  对于100%的数据,n,k<=100000

分析

第一眼看这不是结论题吗?直接就是C(n+k-1,n-1)。

然后一看模数是个偶数,瞬间懵逼

最后直接赌命暴力分解质因数,居然过了。。。。。。

仔细算复杂度应该是n根号n的

代码

#include<cstdio>
const int mod=;
int n,k,mp[];
int qp(int a,int k)
{
int res=;
while(k)
{
if(k&)res=1ll*res*a%mod;
a=1ll*a*a%mod;k/=;
}
return res;
}
int C(int a,int b)
{
int ans=;
for(int i=a,x;i>=a-b+;i--)
{
x=i;
for(int j=;j*j<=x;j++)
while(x%j==)x/=j,mp[j]++;
mp[x]++;
}
for(int i=,x;i<=b;i++)
{
x=i;
for(int j=;j*j<=x;j++)
while(x%j==)x/=j,mp[j]--;
mp[x]--;
}
for(int i=;i<=;i++)ans=1ll*ans*qp(i,mp[i])%mod;
return ans;
}
int main()
{
scanf("%d%d",&n,&k);
printf("%d\n",C(n+k-,n-));
}

最新文章

  1. android 自定义控件——(四)圆形进度条
  2. Height Half Values
  3. Hibernate 所有缓存机制详解
  4. python 安装模块步骤
  5. ubuntu下firefox浏览器flash player插件的安装
  6. 解析HTTP协议六种请求方法,get,head,put,delete,post有什么区别
  7. pt-query-digest用法
  8. go中方法的接收者是值或者指针的区别
  9. ThinkPHP多表联合查询的常用方法
  10. 【Anagrams】 cpp
  11. [Locked] Maximum Size Subarray Sum Equals k
  12. Oracle执行计划——all_rows和first_rows(n) 优化器模式
  13. [html5] 学习笔记-Canvas标签的使用
  14. Newtonsoft.Json 版本冲突时解决方案
  15. Spring对IOC的理解
  16. python下如何安装.whl包?
  17. tensorflow 使用 3 模型学习
  18. windows 2008下IIS7 安装ASP.NET 遇到500.19
  19. connect socket的超时设置
  20. 异常:Instantiation of bean failed; nested exception is java.lang.NoSuchMethodError: com.google.common.base.Preconditions.che ckState(ZLjava/lang/String;I)V

热门文章

  1. 【转载】 C#使用string.IsNullOrWhiteSpace方法判断字符串是否为非空字符
  2. WinServer-开关机日志
  3. 部署python项目到linux服务器
  4. python接口自动化13-data和json参数傻傻分不清
  5. zabbix-proxy及ELK
  6. [ipsec][crypto] ike/ipsec与tls的认证机制比较
  7. python中 &quot;is&quot;和&quot;==&quot;的区别
  8. js基础知识3
  9. Beta版本冲刺
  10. 剑指Offer(三十六):两个链表的第一个公共结点