洛谷P2822组合数问题
2024-08-27 09:19:39
传送门啦
15分暴力，但看题解说暴力分有30分。
就是找到公式，然后套公式。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long read(){
char ch;
bool f = false;
while((ch = getchar()) < '0' || ch > '9')
if(ch == '-') f = true;
int res = ch - 48;
while((ch = getchar()) >= '0' && ch <='9')
res = res * 10 - ch + 48;
return f ? res + 1 : res;
}
long long jc(long long a){
//求阶乘
if(a == 0) return 1;
long long ans = 1;
for(int i=1;i<=a;i++)
ans *= i;
return ans; //b = !a
}
long long C(long long n,long long m){
return jc(n) / (jc(m) * jc(n - m));
}
//组合数公式：Cn^m = !n / (!m * !(n - m))
long long t,k,n,m;
long long sum,x;
int main(){
t = read(); k = read();
while(t--){
x = 0;
n = read(); m = read();
//sum = jc(n) / (jc(m) * jc(n - m));
for(long long i=1;i<=n;i++){
//int j = min(i , m);
for(long long j=1;j<=min(i,m);j++){
//sum = jc(i) / (jc(j) * jc(i - j));
if(C(i,j) % k == 0)
x++;
}
}
printf("%lld\n",x);
}
return 0;
}
15分，我现在用了组合数的递推公式，按理说应该更快了，但。。（想不通，数据范围在那里啊）
c[i][j]即为从i件物品中选j件的方案数。如果第i件物品不选，方案数就变为c[i-1][j]，如果选第i件物品，方案数就变为c[i-1][j-1]，总方案数就为两种情况的方案数之和
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2005;
long long read(){
char ch;
bool f = false;
while((ch = getchar()) < '0' || ch > '9')
if(ch == '-') f = true;
int res = ch - 48;
while((ch = getchar()) >= '0' && ch <='9')
res = res * 10 - ch + 48;
return f ? res + 1 : res;
}
long long t,k,n,m;
long long sum,x,C[maxn][maxn];
int main(){
t = read(); k = read();
while(t--){
x = 0;
C[1][0] = C[1][1] = 1;
n = read(); m = read();
for(long long i=2;i<=n;i++){
C[i][0] = 1;
for(long long j=1;j<=min(i,m);j++){
C[i][j] = C[i-1][j] + C[i-1][j-1];
if(C[i][j] % k == 0)
x++;
}
}
printf("%lld\n",x);
}
return 0;
}
为了提高效率，我们可以进行进一步的优化，就是预处理出组合数从而求出所有区间的满足条件的组合数个数，这里就要用到二维前缀和
杨辉三角
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2005;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
long long t,k,n,m;
long long sum[maxn][maxn],x,C[maxn][maxn];
void work(){
for(int i=1;i<=2000;i++){
C[i][0] = 1;
C[i][i] = 1;
}
C[1][1] = 1;
for(long long i=2;i<=2000;i++)
for(long long j=1;j<i;j++){
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % k;
}
for(long long i=1;i<=2000;i++){
for(long long j=1;j<=i;j++){
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
if(C[i][j] == 0)
sum[i][j]++ ;
}
sum[i][i+1] = sum[i][i];
}
}
int main(){
memset(C,0,sizeof(C));
memset(sum,0,sizeof(sum));
t = read(); k = read();
work();
while(t--){
n = read(); m = read();
m = min(n , m);
printf("%lld\n",sum[n][m]);
}
return 0;
}
还有一个事不得不说，我改了一下午竟然发现是自己的快读打错了：
修改后：
暴力 40分
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
long long jc(long long a){
//求阶乘
if(a == 0) return 1;
long long ans = 1;
for(int i=1;i<=a;i++)
ans *= i;
return ans; //b = !a
}
long long C(long long n,long long m){
return jc(n) / (jc(m) * jc(n - m));
}
//组合数公式：Cn^m = !n / (!m * !(n - m))
long long t,k,n,m;
long long sum,x;
int main(){
t = read(); k = read();
while(t--){
x = 0;
n = read(); m = read();
//sum = jc(n) / (jc(m) * jc(n - m));
for(long long i=1;i<=n;i++){
//int j = min(i , m);
for(long long j=1;j<=min(i,m);j++){
//sum = jc(i) / (jc(j) * jc(i - j));
if(C(i,j) % k == 0)
x++;
}
}
printf("%lld\n",x);
}
return 0;
}
递推公式 70
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2005;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
long long t,k,n,m;
long long sum,x,C[maxn][maxn];
int main(){
t = read(); k = read();
while(t--){
x = 0;
C[1][0] = C[1][1] = 1;
n = read(); m = read();
for(long long i=2;i<=n;i++){
C[i][0] = 1;
for(long long j=1;j<=min(i,m);j++){
C[i][j] = C[i-1][j] + C[i-1][j-1];
if(C[i][j] % k == 0)
x++;
}
}
printf("%lld\n",x);
}
return 0;
}
最新文章
- ssh+expect批量分发
- VPS/云主机 如何试用远程连接登录主机服务器_
- [转载]HDU 3478 判断奇环
- Android编程小实验
- mysql 运行sql脚本文件
- shell中的条件判断
- sharepoint 2013 reporting services 远程server返回错误: (500) 内部server错误。
- android 实现悬架控制
- 配置路线图RouteMap注意事项
- 【转载】什么是Windows USB设备路径，它是如何格式化的？
- 【导航】Python常用资源（从新手到大牛）
- python程序—名片管理系统
- STM32学习笔记：【003】GPIO
- cookies增删改擦操作
- 【刷题】AtCoder Regular Contest 002
- android rom开发
- 前端模板学习bootstrap
- jquery接触初级----jquery 选择器
- Java 基本语法---Java方法
- shell 命令参数