首页 > 代码库 > hihoCoder挑战赛5 C 与链
hihoCoder挑战赛5 C 与链
有两种DP搞法,不过其实本质上是一样的。。。
一种是按照题解上说的记录当前到i位,进位为j的种类数,转移的时候直接枚举在这一位上面放多少个1就好了。
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;typedef long long LL;const LL mod = 1e9 + 9;int bits[64], k, n;LL f[64][10000 + 10];void getbits(int num) { memset(bits, 0, sizeof(bits)); for(int i = 0; i <= 30; i++) bits[i] = (bool)(num & (1 << i));}LL dfs(int now, int over, LL nownum) { if(now == 30) return over == 0; if(nownum > n) return 0; if(f[now][over] != -1) return f[now][over]; LL ret = 0; for(int i = 0; i <= k; i++) { if(nownum + (i << now) > n) break; if((over + i) % 2 == bits[now]) { ret += dfs(now + 1, (over + i - bits[now]) >> 1, nownum + (i << (now))); ret %= mod; } } if(f[now][over] == -1) f[now][over] = ret % mod; return ret % mod;}int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &k, &n); memset(f, -1, sizeof(f)); getbits(n); cout << dfs(0, 0, 0) << endl; } return 0;}
另外一种是记录当前位i构成和为j的种类数,转移的时候也是枚举在当前为放多少个1.
#include <cstdio>#include <cstring>#include <algorithm>#include <map>#include <set>#include <bitset>#include <queue>#include <stack>#include <string>#include <iostream>#include <cmath>#include <climits>using namespace std;const int maxn = 1e4 + 10;typedef long long LL;const LL mod = 1e9 + 9;LL f[30][maxn];int main() { int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d%d", &k, &n); memset(f, 0, sizeof(f)); for(int i = 0; i <= k && i <= n; i++) f[0][i] = 1; for(int i = 0; i < 16; i++) { for(int j = 0; j <= n; j++) if(f[i][j]) { for(int t = 0; t <= k; t++) { LL nxt = ((LL)t << (i + 1)) + j; if(nxt > n) break; f[i + 1][nxt] = (f[i + 1][nxt] + f[i][j]) % mod; } } } cout << f[16][n] << endl; } return 0;}
hihoCoder挑战赛5 C 与链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。