【BZOJ4870】[SHOI2017] 组合数问题(倍增)

点此看题面

大致题意:(sum_{i=0}^{infty}C_{nk}^{ik+r} mod p)

前言

(Jan 28th)刷题计划(4/6),算法标签:DP、倍增。

因为一个小细节死了。

倍增

我们要考虑组合数的本质,(C_n^m)就是在(n)个数中选出(m)个数。

而这道题,就相当于求有多少种方案在(nk)个数中选出(m)个数满足(mequiv r(mod k))

于是设(f_{i,j})表示在(i)个数中选出(m)个数满足(mequiv j(mod k))的方案数,最后答案就是(f_{nk,r})

至于如何(DP),这里考虑倍增的做法。

设当前要求的是(f_{x,0sim k-1}),则:

  • (x)为偶数时,先递归求出(f_{frac x2,0sim k-1}),然后由(f_{x,(i+j)\%k}=f_{frac x2,i}cdot f_{frac x2,j})这个关系式求出(f_x)(就相当于把选出数的个数模(k)((i+j)\%k)分成在前半部分选出数的个数模(k)(i)且在后半部分选出数的个数模(k)(j))。
  • (x)为奇数时,先按上面的方法求出(f_{x-1,0sim k-1}),然后根据(C_n^m=C_{n-1}^m+C_{n-1}^{m-1})得到关系式(f_{x,i}=f_{x-1,i}+f_{x-1,(i-1+k)\%k}),从而求出(f_x)

细节

一般情况下,边界应该设成当(n=1)时,(f_{1,0}=f_{1,1}=1)

但要注意(k=1,r=0)的情况,此时边界为(f_{1,0}=2)(为了这个调了半天)。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define K 50
using namespace std;
int n,k,r,X,f[K+5],g[K+5];
I void Work(Con long long& x)//倍增
{
	#define Copy() for(i=0;i^k;++i) g[i]=f[i],f[i]=0;//把f复制到g,同时清空f
	if(x==1) return (void)(k^1?(f[0]=f[1]=1):(f[0]=2));Work(x>>1);//判边界,否则递归处理
	RI i,j;Copy();for(i=0;i^k;++i) for(j=0;j^k;++j) f[(i+j)%k]=(1LL*g[i]*g[j]+f[(i+j)%k])%X;//动态规划
	if(x&1) {Copy();for(i=0;i^k;++i) f[i]=(g[i]+g[(i-1+k)%k])%X;}//特判奇数情况
}
int main()
{
	return scanf("%d%d%d%d",&n,&X,&k,&r),Work(1LL*n*k),printf("%d",f[r]),0;
}
原文地址:https://www.cnblogs.com/chenxiaoran666/p/BZOJ4870.html