【CSP模拟赛】方程(数学)
2024-10-21 15:48:27
题目描述
求关于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-));
}
最新文章
- android 自定义控件——(四)圆形进度条
- Height Half Values
- Hibernate 所有缓存机制详解
- python 安装模块步骤
- ubuntu下firefox浏览器flash player插件的安装
- 解析HTTP协议六种请求方法,get,head,put,delete,post有什么区别
- pt-query-digest用法
- go中方法的接收者是值或者指针的区别
- ThinkPHP多表联合查询的常用方法
- 【Anagrams】 cpp
- [Locked] Maximum Size Subarray Sum Equals k
- Oracle执行计划——all_rows和first_rows(n) 优化器模式
- [html5] 学习笔记-Canvas标签的使用
- Newtonsoft.Json 版本冲突时解决方案
- Spring对IOC的理解
- python下如何安装.whl包?
- tensorflow 使用 3 模型学习
- windows 2008下IIS7 安装ASP.NET 遇到500.19
- connect socket的超时设置
- 异常:Instantiation of bean failed; nested exception is java.lang.NoSuchMethodError: com.google.common.base.Preconditions.che ckState(ZLjava/lang/String;I)V
热门文章
- 【转载】 C#使用string.IsNullOrWhiteSpace方法判断字符串是否为非空字符
- WinServer-开关机日志
- 部署python项目到linux服务器
- python接口自动化13-data和json参数傻傻分不清
- zabbix-proxy及ELK
- [ipsec][crypto] ike/ipsec与tls的认证机制比较
- python中 ";is";和";==";的区别
- js基础知识3
- Beta版本冲刺
- 剑指Offer(三十六):两个链表的第一个公共结点