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

Nemlit

2019-10-19 16:46:26

Solution

题目是要我们求出如下柿子: $$\sum_{i=0}^{n}C_{nk}^{ik+r}$$ 考虑k和r非常小,我们能不能从这里切入呢? 如果你注意到,所有组合数上方的数$\%k==r$,那么是不是可以从$DP$开始呢? 跟据上述性质,我们可以得到暴力$DP$: 考虑组合数的实际意义是在n个数中选出m个,那么我们可以设$dp[i][j]$表示在i个元素中,选了$m\%k==j$的方案数 转移就可以用$dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]$了,根据你的欧气,你可以获得$45-70$分的分数 由于空间原因,暴力代码用了滚动数组;由于文章长度原因,暴力代码省去了一些没必要的东西 ## $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() { n = read(), p = read(), m = read(), r = read(), dp[0] = 1; 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; } ``` 那么我们还可以怎么优化呢? 考虑到$N*K$达到了$5*10^{10}$,我们考虑矩阵优化: 我们怎么从$dp[i - 1][0……m-1]$推出$dp[i][0……m-1]$呢? 只需要构造一个$50*50$的矩阵,第一行中第一列和最后一列为$1$,其余第$i$行第$i$列和第$i-1$列为1,其他都是$0$,问题便可以解决 注意,矩阵初始化的时候不能直接$=1$,要考虑$k=1$的情况 ## $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define int long long int read() { 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() { n = read(), p = read(), m = read(), r = read(); ++ Base.a[1][1], ++ Base.a[1][m], ++ Ans.a[1][1]; rep(i, 2, m) ++ Base.a[i][i], ++ Base.a[i][i - 1]; Ans = Mul(Ans, Pow(Base, n * m)); printf("%lld", Ans.a[1][1 + r]); return 0; } ```