网站app怎么做,网络服务无法启动,什么网站可以接装修活,wordpress+采集小说http://www.lydsy.com/JudgeOnline/problem.php?id4870 矩阵快速幂。。。 人话题意#xff1a;从nk个物品里选模k余r个物品#xff0c;问方案数模P 那么我们有方程 f[i][j]f[i-1][j]f[i-1][j-1] 跟组合数一个样子 j∈(0,k) 这个物品选还是不选加起来 构造矩阵#xff1a;x.… http://www.lydsy.com/JudgeOnline/problem.php?id4870 矩阵快速幂。。。 人话题意从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][i1]1 自己手画一下 #includebits/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] 所以j1,j-11 }
}
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
