数位DP CF388D - Fox and Perfect Sets
一个整数perfect集合满足性质:集合中随意两个整数的异或和仍在这个集合中。
求最大数不超过K的perfect集合的个数。
每一个集合都是一个线性的向量空间。
。能够通过全然的高斯消元得出该空间的基底。。从高位到低位按基底DP。
。
DP[now][num][upper]表示K从左往右第now位空间向量个数为num且集合中最大值是否为K的前now位的基底个数。。。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <cassert> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #define RD(x) scanf("%d", &x) #define REP(i, n) for (int i=0; i<(n); i++) #define FOR(i, n) for (int i=1; i<=(n); i++) #define pii pair<int, int> #define mp make_pair int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; using namespace std; #define N 50 #define M 22222 #define eps 1e-9 #define pi acos(-1.0) #define inf 0XFFFFFFFll #define mod 1000000007ll #define LL long long int K; LL dp[N][N][2]; LL c[N][N]; int main() { REP(i, N) REP(j, i + 1) { if (j == 0 || j == i) c[i][j] = 1; else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod; } RD(K); dp[31][0][1] = 1; for (int i = 31; i > 0; --i) { for (int j = 0; j <= 30; ++j) { for (int k = 0; k < 2; ++k) { // add new 1 in a new vector if (!(k == 1 && (K >> (i - 1)) % 2 == 0)) { int nk = (k == 1 && (K >> (i - 1)) % 2 == 1) ? 1 : 0; dp[i-1][j+1][nk] += dp[i][j][k]; dp[i-1][j+1][nk] %= mod; } // add new 1 in old vectors even int nk = (k == 1 && (K >> (i - 1)) % 2 == 0) ?1 : 0; for (int t = 2; t <= j; t += 2) { dp[i-1][j][nk] += dp[i][j][k] * c[j][t] % mod; dp[i-1][j][nk] %= mod; } // add new 1 in old vectors odd if (!(k == 1 && (K >> (i - 1)) % 2 == 0)) { int nk = (k == 1 && (K >> (i - 1)) % 2 == 1) ? 1 : 0; for (int t = 1; t <= j; t += 2) { dp[i-1][j][nk] += dp[i][j][k] * c[j][t] % mod; dp[i-1][j][nk] %= mod; } } // be zero nk = (k == 1 && (K >> (i - 1)) % 2 == 0) ?
1 : 0; dp[i-1][j][nk] += dp[i][j][k]; dp[i-1][j][nk] %= mod; } } } LL ans = 0; REP(j, 31) REP(k, 2) ans = (ans + dp[0][j][k]) % mod; cout << ans << endl; return 0; }
相关文章
- What is the difference between ManualResetEvent and AutoResetEvent in .NET?
- HDOJ 5418 Victor and World 状压DP
- 基本3D变换之World Transform, View Transform and Projection Transform
- Codeforces Round #837 (Div. 2) C. Hossam and Trainees
- 【CF613D】Kingdom and its Cities 虚树+树形DP
- [转]mysql问题解决SELECT list is not in GROUP BY clause and contains nonaggregated column
- CodeForces 935E Fafa and Ancient Mathematics (树形DP)
- CodeForces 754C Vladik and chat (DP+暴力)
- HDU 5900 QSC and Master (区间DP)
- HDU 4489 The King’s Ups and Downs (DP+数学计数)
- CoderForces 518D Ilya and Escalator (期望DP)
- CodeForces 611C New Year and Domino (动态规划,DP)
- NGINX Load Balancing – TCP and UDP Load Balancer
- Failed to load module “canberra-gtk-module“ 或 Using GTK+ 2.x and GTK+ 3 in the same process is not
- pat 1006 Sign In and Sign Out(25 分)
- Camera Calibration and 3D Reconstruction
- The Definitive C++ Book Guide and List--reference
- 《Feature-metric Loss for Self-supervised Learning of Depth and Egomotion》论文笔记