洛谷P3746 [六省联考2017]组合数问题

题目描述

组合数 C_n^mCnm​ 表示的是从 n 个互不相同的物品中选出 m 个物品的方案数。举个例子,从 (1;2;3) 三个物品中选择两个物品可以有 (1;2);(1;3);(2;3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 C_n^mCnm​ 的一般公式:

C_n^m = \frac{n!}{m!(n-m)!}Cnm​=m!(n−m)!n!​

其中 n! = 1 × 2 × · · · × n。(特别的,当 n = 0 时, n! = 1 ,当 m > n 时, C_n^m =0Cnm​=0 )

小葱在 NOIP 的时候学习了 C_i^jCij​ 和 k 的倍数关系,现在他想更进一步,研究更多关于组合数的性质。小葱发现, C_i^jCij​ 是否是 k 的倍数,取决于 C_i^j mod kCij​modk 是否等于 0,这个神奇的性质引发了小葱对 mod 运算(取余数)的兴趣。现在小葱选择了是四个整数n; p; k; r,小葱现在希望知道

\sum_{i=0}^{\inf} C_{nk}^{ik+r} mod p∑i=0inf​Cnkik+r​modp

的值。

输入输出格式

输入格式:

第一行有四个整数 n; p; k;r,所有整数含义见问题描述。

输出格式:

一行一个整数代表答案。

输入输出样例

输入样例#1:

2 10007 2 0

输出样例#1: 

8

输入样例#2:

20 10007 20 0

输出样例#2: 

176

说明

• 对于 30% 的测试点, 1 ≤ n; k ≤ 30, p 是质数;

• 对于另外 5% 的测试点, p = 2;

• 对于另外 5% 的测试点, k = 1;

• 对于另外 10% 的测试点, k = 2;

• 对于另外 15% 的测试点, 1 ≤ n ≤ 10^3; 1 ≤ k ≤ 50, p 是质数;

• 对于另外 15% 的测试点, 1 ≤ n × k ≤ 10^6, p 是质数;

• 对于另外 10% 的测试点, 1 ≤ n ≤ 10^9; 1 ≤ k ≤ 50, p 是质数;

• 对于 100% 的测试点, 1 ≤ n ≤ 10^9; 0 ≤ r < k ≤ 50; 2 ≤ p ≤ 2^30 − 1。

作为省选的T3出题人居然给了60分的暴力分,太良心了QWQ..

不过正解是死活想不到啊

设$C[i][j]$表示从$i$个元素中,拿所有满足$x \%k=j $ 的 $x$个元素的方案数

那么对于第$i$个元素,

不选的方案数为$C[i-1][j]$

选的方案数为$C[i-1][(j-1+k)%k]$

很显然

可以用矩阵快速幂优化

然后就做完了

这题的关键是把杨辉三角的递推与题目中给出的式子相结合,找到题目中式子的一般规律,

进而通过更高科技的算法优化

注意$k=1$的特殊情况

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define int long long 
using namespace std;
const int MAXN=1e6;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,mod,k,r;
int C[51][51];
struct Matrix
{
    int a[51][51];
    Matrix(){memset(a,0,sizeof(a));}
};
Matrix mul(Matrix x,Matrix y)
{
    Matrix c;
    for(int kk=0;kk<=k-1;kk++)
        for(int i=0;i<=k-1;i++)
            for(int j=0;j<=k-1;j++)
                c.a[i][j]=(c.a[i][j]+x.a[i][kk]*y.a[kk][j]%mod)%mod;
    return c;
}
void out(Matrix x)
{
    for(int i=0;i<=k-1;i++,puts("\n"))
        for(int j=0;j<=k-1;j++)
            printf("%d ",x.a[i][j]);
}
Matrix fastpow(Matrix a,int p)
{
    Matrix base;
    for(int i=0;i<=k;i++) base.a[i][i]=1;
    while(p)
    {
        if(p&1) base=mul(base,a);
        a=mul(a,a);
        p>>=1;
    }
    return base;
}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    N=read(),mod=read(),k=read(),r=read();
    Matrix tmp;
    for(int i=0;i<=k-2;i++)
        tmp.a[i][i]=tmp.a[i][i+1]=1;
    tmp.a[k-1][0]++;tmp.a[k-1][k-1]++;
    Matrix ans;
    ans.a[0][0]=1;
    tmp=fastpow(tmp,N*k);
    ans=mul(ans,tmp);
    printf("%lld",ans.a[0][r]);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang精编100题

能力模型 级别模型初级 primary熟悉基本语法,能够看懂代码的意图; 在他人指导下能够完成用户故事的开发,编写的代码符合CleanCode规范;中级 int...

427110
来自专栏达摩兵的技术空间

js代码优化日常001

本文开始针对项目中总结出来的关于js基础知识的代码优化技巧进行每个细节点的分析,后续还会针对某个专题的分析。

20330
来自专栏做全栈攻城狮

程序员带你十天快速入门Python,玩转电脑软件开发(四)

本系列文章立志于从一个已经习得一门编程语言的基础之上,全面介绍Python的相关开发过程和相关经验总结。本篇文章主要是基于上一篇的程序员带你十天快速入门Pyth...

9520
来自专栏诸葛青云的专栏

学了指针没学动态内存一切都白搭!C语言基础教程之内存管理

本文将讲解 C 中的动态内存管理。C 语言为内存的分配和管理提供了几个函数。这些函数可以在<stdlib.h>头文件中找到。

12500
来自专栏企鹅号快讯

编程语言学啥?当然首选Python啦!千字长文教你如何入门Python!

1.1 流程控制之for循环 ? 1.2 开发工具IDE 1.2.1 为何要用IDE ? 很多语言都有比较流行的开发工具,比如JAVA 的Eclipse, C#...

46160
来自专栏向治洪

浅谈前端JavaScript编程风格

前言 多家公司和组织已经公开了它们的风格规范,具体可参阅jscs.info,下面的内容主要参考了Airbnb的JavaScript风格规范。当然还有google...

21170
来自专栏Crossin的编程教室

【编程课堂】有序字典 OrderedDict

编程课堂将和每周一坑一样,成为本教室公众号的一个长期固定栏目。每期讲解一个编程知识点,包括但不限于 Python 语法、模块介绍、编程小技巧等。用简短的篇幅,让...

38080
来自专栏gaoqin31

设计模式之 工厂模式

简单工厂模式 : 简单工厂模式是属于创建型的设计模式,又叫做静态工厂方法模式,但不属于23种GOF设计模式,简单工厂模式是由一个工厂决定创建哪一类产品的实例,简...

16050
来自专栏Golang语言社区

Golang语言--资源自动回收技术

Go语言作为一个现代化的编程语言以及支持垃圾内存的自动回收特性(GC). 我们现在关注的是非内存资源的自动回收技术. 局部资源的管理 在讨论Go语言解决方案之前...

42880
来自专栏Java后端技术栈

关于Java代码优化的N条建议!

本文是作者:五月的仓颉 结合自己的工作和平时学习的体验重新谈一下为什么要进行代码优化。在修改之前,作者的说法是这样的:

13620

扫码关注云+社区

领取腾讯云代金券