D. Beautiful numbers ?代碼
P3646[APIO2015]巴厘島的雕塑 ?代碼

?代碼

LL a[N]; int mi[N]; int main() {int n, A, B;scanf("%d%d%d", &n, &A, &B);for(int i = 1;i <= n;i ++) scanf("%lld", a+i);LL x = (1LL<<44)-1; // 貪心選for(int i = 43;i >= 0;i --){x ^= 1LL<<i;bitset<101> c[2100]; // 當(dāng)A != 1 時 好像沒被卡 5e8的復(fù)雜度了。c[n+1][0] = 1; // A = 1 時 只用看最小的就行。for(int i = n;i >= 1;i --){mi[i] = B+1;LL sum = 0;for(int j = i;j <= n;j ++) // 麻了， j 從頭i開始 wa半天{sum += a[j];if((sum|x) == x)A == 1 ? mi[i] = min(mi[i], mi[j+1]+1) : c[i] |= c[j+1]<<1;}}if(A == 1) {if(mi[1] > B) x ^= 1LL<<i; }else{bool f = 0;for(int i = A;i <= B;i ++)f |= c[1][i];if(!f) x ^= 1LL<<i; }}cout<<x<<endl;return 0; }

第一次把18位LL變成11位int+7位LL存，但是還是T了，結(jié)果發(fā)現(xiàn)倍數(shù)只有48種，那就枚舉了，麻了麻了。

LL dp[18][50][2520];// = t*2520 + x = (t*f + x/z)*z + x%z; // dp[i][j][k] = i位 0-9=j %2520=k 的情況數(shù). int in[100], pos[N]; vector<int> G;int lcm(int a, int b){if(!a||!b) return b+a;return a*b/__gcd(a, b);} int SE(int i) {int x = 1;for(int j = 1;j <= 9;j ++) if(i>>j&1) x = lcm(x, j);return x; }void ini() {for(int i = 0;i < 1<<10;i ++) G.push_back(SE(i));sort(G.begin(), G.end());G.erase(unique(G.begin(), G.end()), G.end()); for(int i = 0;i < G.size(); i ++) pos[G[i]] = i;in[0] = 1;for(int i = 1;i <= 18;i ++) in[i] = in[i-1]*10%C; for(int i = 0;i <= 9;i ++) dp[0][pos[SE(1<<i)]][i] = 1;for(int i = 1;i <= 17;i ++)for(int j = 0;j <= 9;j ++)for(int l = 0;l < G.size();l ++)for(int k = 0;k < C;k ++)if(j) dp[i][pos[lcm(G[l], j)]][(k+j*in[i])%C] += dp[i-1][l][k];else dp[i][l][k] += dp[i-1][l][k];return ; }LL se(LL up) {vector<int> v;if(up == 0) return 1;while(up) v.push_back(up%10), up /= 10;int x = 0, ox = 0;LL sum = 0;for(int i = v.size()-1;i >= 1;i --){for(int j = 0;j < v[i];j ++){int L = j*in[i]%C;for(int k = 0;k < G.size();k ++)for(int f = 0, len = lcm(G[k], SE(ox|1<<j));f < 2520;f += len)sum += dp[i-1][k][(f-L-x+C+C)%C];} x = (x + v[i]*in[i])%C; ox |= 1<<v[i];} for(int i = 0;i <= v[0];i ++)sum += (x+i)%SE(ox|1<<i) == 0;return sum; }int main() {ini();int t;scanf("%d",&t);while(t --){LL l, r;scanf("%I64d%I64d", &l, &r);printf("%I64d\n", se(r) - se(l-1));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的dpdpdp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。