【JAG Autumn 2014, MIPT2014 G 2595】（前缀和优化组合数dp）

本文主要是介绍【JAG Autumn 2014, MIPT2014 G 2595】（前缀和优化组合数dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接:

http://opentrains.snarknews.info/~ejudge/sn_sh.cgi?data=result_team&sid=b2c98fc49b3509f3

题意：有n块饼干，明天吃不多于x块，问在d天之前吃完的方法数

1<=n<=2000

1<=d<=1e12

1<=x<=2000

分析：观察数据，发现d很小，那么我们可以从n,x入手解决，可以发现当d很大的时候，会有很多0，并且0的个数最多n个.抛开0的天数，设计出dp[i][j]表示i天吃了j块饼干的方法数。

阶段：天数

转移方程：dp[i][j]=sum(dp[i-1][j-k]|k=[1,x))

 状态非常大，（n^2枚举）,观察可以得到，当外层循环一定是，就是求i-1时的(j-1)-(j-x+1)的和，可以使用树状数组维护，或者前缀和维护更新

初始状态：dp[0][0]=1;

目标：ans=sum(dp[i][n]*c[i,d]|i=[1,min(n,d)])

代码：

#pragma warning(disable:4996)
#include<bits/stdc++.h>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<math.h>
const int maxn = 2003;
typedef long long ll;
const ll mod =(ll) (1e9 + 7);
ll dp[maxn][maxn];
ll C[maxn][maxn];
ll sum[maxn][maxn];
/*dp[i][j]=sum(dp[i-1][j-k]|k=[1,x))O(n^2)sum(dp[i][n]*C(i,d)|i=[1,min(n,d)])
*/
ll n, d, x;ll qpow(ll a, ll b){ll ans = 1, base = a;while (b){if (b & 1)ans =ans* base%mod;base = base*base%mod;b >>= 1;}return ans;
}void init() {for (ll i = 0; i <= 2002; i++) {sum[0][i] = 1;}
}int main() {while (~scanf("%lld%lld%lld", &n, &d, &x),(n+d+x)) {init();dp[0][0] = 1;for (ll i = 1; i <= n; i++) {for (ll j = i; j <= n; j++) {dp[i][j] = (sum[i-1][j - 1] - (j - x < 0 ? 0 : sum[i - 1][j - x]) + mod) % mod;}for (ll j = 0; j < n; j++) {sum[i][j + 1] = (sum[i][j] + dp[i][j + 1]) % mod;}}ll res = 0;ll mi = n;if (n > d)mi = d;ll c = 1;for (ll i = 1; i <= mi; i++) {(c*=(d-i+1)%mod) %= mod;(c*=(qpow(i,mod-2))) %= mod;(res+=dp[i][n]*c) %= mod;}printf("%lld\n", res);}
}

 

这篇关于【JAG Autumn 2014, MIPT2014 G 2595】（前缀和优化组合数dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---