六省联考2017 组合数问题

wjh15101051's space

卧薪尝胆，厚积薄发。

六省联考2017 组合数问题

Date: Fri Sep 07 20:00:54 CST 2018

In Category: NoCategory

Description：

求 $\begin{align}\sum_{i=0}^{\infty}C^{ik+r}_{nk}\%\ p\end{align}$

$1\le n \le 10^9,0 \le r < k \le 50$

Solution：

式子的实际意义是在 $nk$ 个物品里面选出的数的个数 $\%k=r$ 的方案数，设其为 $F[nk][r]$

$F[i][j]=F[i-1][j]+F[i-1][(j-1-1+k)\%k+1]$

这个转移的效果就是把整个矩阵循环移一位再加到原来的矩阵中，不看实际意义直接构造递推也可以。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,p,w,r;

#define MAXK 51

struct matrix

{

	ll m[MAXK][MAXK];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= w;++i)

			for(int j = 1;j <= w;++j)

				for(int k = 1;k <= w;++k)

					c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % p) % p;

		return c;

	}

	friend matrix operator ^ (matrix a,ll b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}f;

int main()

{

	scanf("%lld%lld%lld%lld",&n,&p,&w,&r);

	for(ll i = 1;i <= w;++i)

	{

		f.m[i][i]++;

		f.m[(i - 1 - 1 + w) % w + 1][i]++;

	}

	f = f ^ (n * w);

	cout << f.m[1][r + 1] << endl;

	return 0;

}

In tag: DP-矩阵加速

wjh15101051