【枚举子序列+组合数学+推式子】Cf Edu11 E

刺骨的言语ヽ痛彻心扉 2024-03-08 08:21 106阅读 0赞

[https://codeforces.com/contest/660/problem/E][https_codeforces.com_contest_660_problem_E]

题意：

![5487fdee8d234851a9d1953b67fb165d.png][]

思路：

重点在于枚举子序列，一般是先枚举子序列长度，然后枚举别的

算是经典套路

![df1cdcb66cf34ee9b970055219e952c1.png][]

![68a1e3d052654d2bb09c4c2855f410f7.png][]

![4afc32a0312f4379af6622a305ef1593.png][]

![08b9ba8a7456467abde0c650acb85131.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e3 + 10;
    constexpr int M = 1e6 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    int n, m;
    
    int qpow(int a, int b) {
        int res = 1;
        while(b) {
            if (b & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }
    void solve() {
        std::cin >> n >> m;
    
        int ans = qpow(m, n) % mod;
        for (int j = 0; j <= n - 1; j ++) {
            ans += qpow(m, n - j) * qpow(2 * m - 1, j) % mod;
            ans %= mod;
        }
    
        std::cout << ans % mod << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[https_codeforces.com_contest_660_problem_E]: https://codeforces.com/contest/660/problem/E
[5487fdee8d234851a9d1953b67fb165d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/99138e04a4a049b98c6ac427a162be55.png
[df1cdcb66cf34ee9b970055219e952c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/c0d92e5a25b4454e912a76df5313bb8d.png
[68a1e3d052654d2bb09c4c2855f410f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/d4dd9e4630544c1785a8936c76129dcb.png
[4afc32a0312f4379af6622a305ef1593.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/fbb203a47ab04449a4f8d21f4739c142.png
[08b9ba8a7456467abde0c650acb85131.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/426886156a6242fe997061456ed8987f.png