数位dp
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 int d[22]; 6 LL po[22], f[22][2][9]; 7 LL cal(LL x){ 8 int b = 0; 9 while(x) d[++b] = x % 10, x /= 10; 10 memset(f, 0, sizeof(f)); 11 f[b+1][1][0] = 1; 12 for(int i = b + 1; i >= 2; i--){ 13 for(int j = 0; j <= 1; j++){ 14 for(int k = 0; k < 9; ++k){ 15 if(!f[i][j][k]) continue; 16 for(int nxt = 0; nxt < 9; ++nxt){ 17 if(j && nxt > d[i-1]) continue; 18 int nj = j && (nxt == d[i-1]); 19 int nk = (k + po[i-2] * nxt) % 9; 20 f[i-1][nj][nk] += f[i][j][k]; 21 } 22 } 23 } 24 } 25 LL ret = 0; 26 for(int i = 1; i < 9; ++i) ret += f[1][0][i] + f[1][1][i]; 27 return ret; 28 } 29 30 int main(){ 31 freopen("A-large.in", "r", stdin); 32 freopen("A-large.out", "w", stdout); 33 po[0] = 1; 34 for(int i = 1; i < 22; i++) po[i] = po[i-1] * 10 % 9; 35 int T; 36 scanf("%d", &T); 37 for(int kase = 1; kase <= T; ++kase){ 38 LL F, L; 39 cin >> F >> L; 40 LL ans = cal(L) - cal(F) + 1; 41 printf("Case #%d: %lld ", kase, ans); 42 } 43 return 0; 44 }
B. Sherlock and the Bit Strings
两边dp枚举中间
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL INF = 1e18; 5 typedef pair<int, int> pii; 6 vector<pii> A[111], B[111]; 7 LL pre[111][1<<16], suf[111][1<<16]; 8 int d[111]; 9 10 bool check_pre(int b, int msk){ 11 bool ret = true; 12 for(int i = 0; i < B[b].size(); ++i){ 13 int a = B[b][i].first, c = B[b][i].second; 14 int tmp = msk & ((1 << (b - a + 1)) - 1); 15 if(__builtin_popcount(tmp) != c) ret = false; 16 } 17 return ret; 18 } 19 20 bool check_suf(int a, int msk){ 21 bool ret = true; 22 for(int i = 0; i < A[a].size(); ++i){ 23 int b = A[a][i].first, c = A[a][i].second; 24 int tmp = msk >> (15 - b + a); 25 if(__builtin_popcount(tmp) != c) ret = false; 26 } 27 return ret; 28 } 29 30 int main(){ 31 freopen("B-large-practice.in", "r", stdin); 32 freopen("B-large-practice.out", "w", stdout); 33 int T; 34 scanf("%d", &T); 35 for(int kase = 1; kase <= T; ++kase){ 36 int N, K; 37 LL P; 38 scanf("%d %d %lld", &N, &K, &P); 39 for(int i = 0; i <= N + 1; ++i) A[i].clear(), B[i].clear(); 40 for(int i = 1; i <= K; ++i){ 41 int a, b, c; 42 scanf("%d %d %d", &a, &b, &c); 43 A[a].push_back(pii(b, c)); 44 B[b].push_back(pii(a, c)); 45 } 46 if(N < 16){ 47 for(int i = 0; i < (1 << N); ++i){ 48 for(int j = 1; j <= N; ++j) d[j] = i & (1 << (N - j)) ? 1 : 0; 49 int ok = 1; 50 for(int j = 1; j <= N; ++j){ 51 for(int k = 0; k < A[j].size(); ++k){ 52 int tmp = 0; 53 for(int p = j; p <= A[j][k].first; ++p) tmp += d[p]; 54 if(tmp != A[j][k].second) ok = 0; 55 } 56 for(int k = 0; k < B[j].size(); ++k){ 57 int tmp = 0; 58 for(int p = B[j][k].first; p <= j; ++p) tmp += d[p]; 59 if(tmp != B[j][k].second) ok = 0; 60 } 61 } 62 P -= ok; 63 if(P == 0){ 64 printf("Case #%d: ", kase); 65 for(int i = 1; i <= N; i++) printf("%d", d[i]); puts(""); 66 break; 67 } 68 } 69 continue; 70 } 71 memset(pre, 0, sizeof(pre)); 72 for(int j = 0; j < (1 << 16); ++j){ 73 int ok = 1; 74 for(int k = 1; k <= 16; ++k) 75 if(!check_pre(k, j >> (16 - k))) ok = 0; 76 pre[0][j] = ok; 77 } 78 for(int i = 0; i < N - 16; ++i){ 79 for(int j = 0; j < (1 << 16); j++){ 80 if(!pre[i][j]) continue; 81 for(int k = 0; k <= 1; ++k){ 82 int nj = (j << 1) & ((1 << 16) - 1); 83 nj |= k; 84 if(!check_pre(i + 17, nj)) continue; 85 if(!check_suf(i + 1, j)) continue; 86 pre[i+1][nj] += pre[i][j]; 87 pre[i+1][nj] = min(pre[i+1][nj], INF); 88 } 89 } 90 } 91 memset(suf, 0, sizeof(suf)); 92 for(int j = 0; j < (1 << 16); ++j){ 93 int ok = 1; 94 for(int k = 1; k <= 16; ++k) 95 if(!check_suf(N - 16 + k, (j << (k - 1)) & ((1 << 16) - 1))) ok = 0; 96 suf[N+1][j] = ok; 97 } 98 for(int i = N + 1; i > 17; --i){ 99 for(int j = 0; j < (1 << 16); j++){ 100 if(!suf[i][j]) continue; 101 for(int k = 0; k <= 1; ++k){ 102 int nj = (j >> 1) | (k << 15); 103 if(!check_suf(i - 17, nj)) continue; 104 if(!check_pre(i - 1, j)) continue; 105 suf[i-1][nj] += suf[i][j]; 106 suf[i-1][nj] = min(suf[i-1][nj], INF); 107 } 108 } 109 } 110 int msk; 111 for(int j = 0; j < (1 << 16); ++j){ 112 LL tmp = pre[0][j] * suf[17][j]; 113 if(tmp >= P){ 114 msk = j; 115 break; 116 } 117 P -= tmp; 118 } 119 for(int i = 1; i <= N - 16; ++i){ 120 d[i] = msk >> 15; 121 msk = (msk << 1) & ((1 << 16) - 1); 122 if(pre[i][msk] && suf[i+17][msk] >= P) continue; 123 P -= suf[i+17][msk]; 124 msk ^= 1; 125 } 126 for(int i = N; i >= N - 15; --i) d[i] = msk % 2, msk /= 2; 127 printf("Case #%d: ", kase); 128 for(int i = 1; i <= N; i++) printf("%d", d[i]); puts(""); 129 } 130 return 0; 131 }