# Nemlit 的博客

By a konjac

### 题解 P3746 【[六省联考2017]组合数问题】

posted on 2019-10-19 16:46:26 | under 题解 |

## $Brute:$

#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
int n, m, p, r, dp[55];
int main() {
rep(i, 1, n * m) {
int pax = dp[m - 1];
drep(j, 1, m - 1) dp[j] = (dp[j - 1] + dp[j]) % p;
dp[0] = (dp[0] + pax) % p;
}
printf("%d", dp[r]);
return 0;
}


## $Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(int i = s; i <= t; ++ i)
int n, m, p, r;
struct Martix {
int a[55][55];
void Init() { rep(i, 1, m) a[i][i] = 1; }
void Mem() { memset(a, 0, sizeof(a)); }
}Ans, Base;
Martix Mul(Martix a, Martix b) {
Martix c; c.Mem();
rep(i, 1, m) rep(j, 1, m) rep(k, 1, m) c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % p) % p;
return c;
}
Martix Pow(Martix a, int b) {
Martix R; R.Mem(), R.Init();
while(b) {
if(b & 1) R = Mul(R, a);
a = Mul(a, a), b >>= 1;
}
return R;
}
signed main() {