分析

如果至少有一组解，则要 \(y\) 被 \(x\) 整除，也就是说 \(a_i\) 一定是 \(x\) 的倍数，可设 \(dp[i]\) 为 和为 \(i\) 且 \(gcd = 1\) 时的方案数，首先呢，如果不考虑 \(gcd\) 的限制，可以发现，\(dp[i]=1<<(i-1)\) ，那么我们只要减去那些 \(gcd > 1\) 的方案数，枚举因子就好了，记忆化搜索即可。

code

#include 
    
     using namespace std;const int MOD = 1e9 + 7;long long p2(int x) {    long long a = 1, k = 2;    while (x) {        if (x & 1) a = a * k % MOD;        k = k * k % MOD;        x >>= 1;    }    return a;}map
     
       dp;long long dfs(int x) {    if (dp.count(x)) return dp[x];    long long res = p2(x - 1);    for (int i = 1; i * i <= x; i++) {        if (x % i == 0) {            if (i != 1) {                res = (res - dfs(x / i) + MOD) % MOD;            }            if(i * i != x) res = (res - dfs(i) + MOD) % MOD;        }    }    return dp[x] = res;}int main() {    dp[1] = 1;    int x, y, n;    long long ans = 0;    cin >> x >> y;    if (y % x == 0) {        ans = dfs(y / x);    }    cout << ans << endl;    return 0;}
     
    

分析

\(dp[i]\) 表示从 \(i\) 开始（\(s[i...n-1]\)）所能构成的不相交 \(t\) 串的最多个数，并维护最小花费 \(mn[i]\) 。

code

#include
    
     using namespace std;const int N = 1e5 + 10;string s;int dp[N], mn[N], ab[N];int main() {    int n, m, k = 0;    cin >> n >> s >> m;    for (int i = n - 1; i >= 0; i--) {        if(s[i] == '?') k++;        if(s[i] == '?' || s[i] == 'a') {            if(s[i + 1] == 'b' || s[i + 1] == '?') ab[i] = ab[i + 2] + 2;            else ab[i] = 1;        }        if(n - i >= m) {            dp[i] = dp[i + 1];            mn[i] = mn[i + 1];            if(ab[i] >= m) {                if(dp[i + m] + 1 > dp[i]) {                    dp[i] = dp[i + m] + 1;                    mn[i] = mn[i + m] + k;                } else if(dp[i + m] + 1 == dp[i]) {                    mn[i] = min(mn[i], mn[i + m] + k);                }            }            if(s[i + m - 1] == '?') k--;        }    }    cout << mn[0] << endl;    return 0;}