bzoj4870

http://www.lydsy.com/JudgeOnline/problem.php?id=4870

矩阵快速幂。。。

人话题意：从nk个物品里选模k余r个物品，问方案数模P

那么我们有方程 f[i][j]=f[i-1][j]+f[i-1][j-1] 跟组合数一个样子 j∈(0,k) 这个物品选还是不选加起来

构造矩阵：x.a[0][0]=1 0个里选0个的方案是1 g.a[i][i]=1 g.a[i][i+1]=1 自己手画一下

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 60; struct mat {ll a[N][N]; } x, g; ll n, k, p, r; void build() {x.a[0][0] = 1; //0个物品选0个的方案数为1 for(int i = 0; i < k; ++i) {++g.a[i][i]; ++g.a[i][(i + 1) % k]; //矩阵的系数 f[i][j]=f[i-1][j]+f[i-1][j-1] 所以j=1,j-1=1 } } mat operator * (const mat &A, const mat &B) {mat ret; memset(ret.a, 0, sizeof(ret.a));for(int i = 0; i < k; ++i)for(int j = 0; j < k; ++j)for(int x = 0; x < k; ++x) ret.a[i][j] = (ret.a[i][j] + A.a[i][x] * B.a[x][j]) % p;return ret; } void power(mat A, ll t) {for(; t; A = A * A, t >>= 1) if(t & 1) x = x * A; } int main() {scanf("%lld%lld%lld%lld", &n, &p, &k, &r);build();power(g, n * k);printf("%lld\n", x.a[0][r]);return 0; } View Code

 

转载于:https://www.cnblogs.com/19992147orz/p/6777314.html

总结

以上是生活随笔为你收集整理的bzoj4870的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。