BZOJ4870：[SHOI2017]组合数问题——题解

朱雀 2021-03-28 15:31 378阅读 0赞

> ![](/images/20210328/1616945460274.png)
> 
>

看网上一群人说“傻逼题”，我感觉我傻逼了。

首先我们把式子转换一下变成求有nk件物品，我取的物品数%k==r的方案数有多少。

显然f\[i\]\[j\]=f\[i-1\]\[j\]+f\[i-1\]\[j-1\]。

但就没人教一下f\[i\]\[j\]=f\[i-1\]\[j\]+f\[i-1\]\[j-1\]如何矩乘吗……

那我就引洛谷的题解了：

> 可以加速的原理，其实就是杨辉三角是一个一维递推，并且可以将递推描述为：复制矩阵到一个新矩阵，然后矩阵右移一格，加到新矩阵中。

#include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll n,p,K,r;
    struct node{
        ll g[51][51];
        node(){
            memset(g,0,sizeof(g));
        }
        friend node operator *(const node &x,const node &y){
            node z;
            for(int i=0;i<K;i++)
                for(int j=0;j<K;j++)
                    for(int k=0;k<K;k++)
                        z.g[i][k]=(z.g[i][k]+x.g[i][j]*y.g[j][k]%p)%p;
            return z;
        }
    }f,t,res;
    int main(){
        cin>>n>>p>>K>>r;
        t.g[0][0]=1;
        for(int i=0;i<K;i++){
            f.g[(i-1+K)%K][i]++;
            f.g[i][i]++;
            res.g[i][i]=1;
        }
        n*=K;
        while(n){
            if(n&1)res=res*f;
            f=f*f;n>>=1;
        }
        printf("%lld\n",(t*res).g[0][r]);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，378人围观）

还没有评论，来说两句吧...

相关阅读

相关【题解】BZOJ P1057 dp

悬线法部分内容参考Santiego的博客，侵删！侵删！侵删！ -------------------- 0x00 关于悬线法只是因为这题用到了不然我干嘛写它

╰半夏微凉°/ 2023年08月17日 16:49/ 0 赞/ 58 阅读

相关 hdu 4870

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=4870][http_acm.hdu.edu.cn_showproblem.ph

缺乏、安全感/ 2022年09月20日 15:26/ 0 赞/ 56 阅读

相关 bzoj 1026——windy 数

思想很简单，但是由于在这道题上犯二，此题让我改到吐血，代码能力还是很差。题意： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为

拼搏现实的明天。/ 2022年08月13日 16:41/ 0 赞/ 99 阅读

相关 BZOJ4415:[SHOI2013]发牌(线段树)

Description 假设一开始，荷官拿出了一副新牌，这副牌有N张不同的牌，编号依次为1到N。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为1, 2,……直到

Myth丶恋晨/ 2022年01月10日 03:49/ 0 赞/ 163 阅读

相关 Bzoj1933 [Shoi2007]Bookcase 书柜的尺寸

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 554 Solved: 212 Description Tom不喜欢那种

朱雀/ 2021年12月17日 15:55/ 0 赞/ 150 阅读

相关【题解】 bzoj2982: combination （Lucas定理）

[题面戳我][Link 1] Solution 板子题 Code //It is coded by ning_mew on 7.25 includ

落日映苍穹つ/ 2021年10月25日 12:34/ 0 赞/ 173 阅读

相关【bzoj4418】[Shoi2013]扇形面积并扫描线+线段树

题目描述给定N个同心的扇形，求有多少面积，被至少K个扇形所覆盖。输入第一行是三个整数n，m，k。n代表同心扇形的个数，m用来等分 \[-π,π\]的弧度。从第二

- 日理万妓/ 2021年10月01日 01:54/ 0 赞/ 228 阅读

相关题解 [BZOJ4144] Petrol

题目描述有一张 n 个点 m 条边的无向图，其中有 s 个点上有加油站。有 Q 次询问(a,b,c)，问能否开一辆油箱容积为 c 的车从 a 走到 b.(a,b均

偏执的太偏执、/ 2021年09月30日 07:48/ 0 赞/ 211 阅读

相关 BZOJ2242：[SDOI2011]计算器——题解

[https://www.lydsy.com/JudgeOnline/problem.php?id=2242][https_www.lydsy.com_JudgeOnline_

灰太狼/ 2021年09月20日 09:36/ 0 赞/ 204 阅读

相关 BZOJ4870：[SHOI2017]组合数问题——题解

看网上一群人说“傻逼题”，我感觉我傻逼了。首先我们把式子转换一下变成求有nk件物品，我取的物品数%k==r的方案数有多少。显然f[i][j]=f[i-1][j]+...

朱雀/ 2021年03月28日 15:31/ 0 赞/ 379 阅读