26牛客寒假算法训练营1题解，如何巧妙为？

26牛客寒假算法训练营1题解 学习总结 学习到了状态压缩，我们直接转换为二进制，再直接把二进制转换为数字就可以了。 用的时候这样用就可以了 x>>j. 对于多种选择方案用状态压缩有时候会解决很多问题 A.A+B Problem 题目描述 有八个独立的数位显示器，每个显示器的每个二极管被点亮的概率为 ，管与管之间互相独立，显示器 之间也相互独立，求分别显示出两个四位合法数字，且数字之和等于输入的常数 的概率。 每个显示器至少亮 1 根（不能全灭） 每个显示器显示的是合法数字 0..9 0..90..9 上排 4 个拼成四位数 A AA，下排 4 个拼成四位数 B BB，满足 A + B = C A+B=CA+B=C（允许前导 0） 解题 我们可以去先算显示当个数d的概率，七段码，每一个对应两种状态，0，1 那我们完全可以用状态压缩来得到这个所以的情况。 例如 显示0 01110111 也就是119，其他的以此类推。 然后我们可以得到每一个数的概率，因为每一个都要亮的概率，所以我们先把每一个数的概率算出来，用 x>>j&1来得到这个数到底是1还是0 最后直接把一个四位数的表示方法写出来，我们直接用取最后一位一直取，如果不够就直接前导零，然后相乘概率。 得到c的话直接枚举a，然后得到b=c-a； 解题代码 #include<bits/stdc++.h> #define int long long #define lll __uint128_t #define PII pair<int ,int> #define endl '\n' using namespace std; #define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印 #define YN(ans) printf("%s\n", (ans)?"YES":"NO"); #define REP(i, e) for (int i = 0; i < (e); ++i) #define REP1(i, s, e) for (int i = (s); i <=(e); ++i) #define TESTS int t; cin >> t; while (t--) #define TEST const int N=2e5+10,M=1e3+10,mod=1e9+7,MOD=998244353; int a[N],b[N],c[N],pre[N]; //相当于0的话就中间那个不亮，1110111，以此类推。 int segMask[10] = { 119, 36, 93, 109, 46, 107, 123, 37, 127, 111 }; int ksm(int p,int q,int mod){ int result=1; p%=mod; while(q){ if(q&1)result=result*p%mod; p=p*p%mod; q>>=1; } return result%mod; } signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int inv100=ksm(100,MOD-2,MOD); int x[7]; int C; cin>>C; //先得到这个，x[i] = p_i / 100 (mod MOD) for(int i=0;i<7;i++){ int p; cin>>p; x[i]=(1ll*p%mod*inv100)%mod; } vector<int>x1(10,1);//统计出0-9这些数在一个的时候的概率。