首页 > 代码库 > hdu 4901
hdu 4901
计数dp
做不出来真是惭愧。。。
#include <cstdio>#include <cstdlib>#include <cmath>#include <stack>#include <vector>#include <sstream>#include <cstring>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <iostream>#define FFI freopen("in.txt", "r", stdin)#define maxn 200010#define INF 0x3f3f3f3f#define inf 10000000#define MOD 1000000007#define ULL unsigned long long#define LL long long#define _setm(houge) memset(houge, INF, sizeof(houge))#define _setf(houge) memset(houge, -1, sizeof(houge))#define _clear(houge) memset(houge, 0, sizeof(houge))using namespace std;LL f[1100][1100], g[1100][1100], h[1100][1100];int a[1100], n;void init() { _clear(f); _clear(g); _clear(h);}void dp() { f[1][a[1]] = 1; for(int i = 2; i <= n; ++ i) { f[i][a[i]] ++; for(int s = 0; s < 1024; ++ s) { f[i][s^a[i]] += f[i-1][s]; f[i][s] += f[i-1][s]; f[i][s^a[i]] %= MOD; f[i][s] %= MOD; } } g[n][a[n]] = h[n][a[n]] = 1; for(int i = n-1; i >= 1; -- i) { g[i][a[i]] ++; h[i][a[i]] ++; for(int s = 0; s < 1024; ++ s) { g[i][s&a[i]] += h[i+1][s]; h[i][s&a[i]] += h[i+1][s]; h[i][s] += h[i+1][s]; g[i][s&a[i]] %= MOD; h[i][s&a[i]] %= MOD; h[i][s] %= MOD; } }}int main(){ int t; scanf("%d", &t); while(t --) { scanf("%d", &n); for(int i = 1; i <= n; ++ i) { scanf("%d", &a[i]); } init(); dp(); LL ans = 0; for(int i = 1; i < n; ++ i) { for(int j = 0; j < 1024; ++ j) { ans = (ans+f[i][j]*g[i+1][j])%MOD; } } printf("%I64d\n", ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。