Codeforces 900D/E

128 阅读 0 评论 85 点赞

我是靠谱客的博主能干裙子，这篇文章主要介绍Codeforces 900D/E，现在分享给大家，希望可以做个参考。

题目链接: http://codeforces.com/contest/900

D题意：给出x, y，求满足下列2个条件的序列数目。
$1. Sigma_{i=1}^na_i = y$
$2. gcd(a_1,a_2,...,a_n) = x$

题解：首先易知，y % x != 0, 则一定不存在这样的数列，答案为0。
　　　否则数列每个数都除去x,可以转化为求有多少个数列满足gcd为1且和为 $frac{y}x$ 。
设 f(t) 为有多少个数列满足gcd为1且和为 t 。
设 g(t) 为有多少个数列满足和为 t 。
可以得到下式：
　　　　　　　　　　 $g(t) = sum_{d|t}f(frac{t}d)$
解法一:记忆化搜索，直接计算 $f(t)$ ,其中算的时候要容斥一下,初始隔板法想一下便知 $mp[x] = 2^{t-1},减去他因子的mp[d]$

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1E9 + 7;
map<int, int>mp;
ll quick(ll a, ll k) //a^k^mod
{
    ll res = 1;
    while(k) {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
ll solve(int x)
{
    if(x == 1) return 1;
    if(mp.count(x)) return mp[x];
    mp[x] = quick(2ll, x-1ll);
    for(int i = 2;i * i <= x;i ++) {
        if(x % i == 0) {
            mp[x] = (mp[x] - solve(x / i) + mod) % mod;
            if(i != x / i) {
                mp[x] = (mp[x] - solve(i) + mod) % mod;
            }
        }
    }
    mp[x] = (mp[x] - 1 + mod) % mod;
    return mp[x];
}
int main()
{
    int x, y;
    scanf("%d%d",&x,&y);
    if(y % x) {
        puts("0");
    } else {
        y /= x;
        printf("%lldn", solve(y));
    }
    return 0;
}

2.莫比乌斯函数。
因为 $g(t) = sum_{d|t}f(frac{t}d) ,且g(t) = 2^{t-1}, 所以f(t) = sum_{d|t}u(d)g(frac{t}d)$

复制代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int u(int n)
{
    if(n == 1) return 1;
    int res = 1;
    for(int i = 2;i * i <= n;i ++) {
        if(n % i == 0) {
            res *= -1;
            int k = 0;
            while(n % i == 0) {
                k ++;
                n /= i;
                if(k > 1) {
                    return 0;
                }
            }
        }
    }
    if(n > 1) res *= -1;
    return res;
}
ll qmod(ll a, ll k) // a^k
{
    ll res = 1;
    while(k) {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
ll gao(ll x)
{
    ll res = 0;
    for(int i = 1;i * i <= x;i ++) {
        if(x % i == 0) {
            res = (res + qmod(2ll, x/i-1ll) * u(i)) % mod;
            if(i != x / i) {
                res = (res + qmod(2ll, i - 1ll) * u(x / i)) % mod;
            }
        }
    } return res;
}
int main()
{
    int x, y;
    scanf("%d%d",&x,&y);
    if(y % x) {
        return puts("0"), 0;
    } else {
        return printf("%lldn",(gao(y/x)%mod+mod)%mod), 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int u(int n)
{
    if(n == 1) return 1;
    int res = 1;
    for(int i = 2;i * i <= n;i ++) {
        if(n % i == 0) {
            res *= -1;
            int k = 0;
            while(n % i == 0) {
                k ++;
                n /= i;
                if(k > 1) {
                    return 0;
                }
            }
        }
    }
    if(n > 1) res *= -1;
    return res;
}
ll qmod(ll a, ll k) // a^k
{
    ll res = 1;
    while(k) {
        if(k & 1) res = res * a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
ll gao(ll x)
{
    ll res = 0;
    for(int i = 1;i * i <= x;i ++) {
        if(x % i == 0) {
            res = (res + qmod(2ll, x/i-1ll) * u(i)) % mod;
            if(i != x / i) {
                res = (res + qmod(2ll, i - 1ll) * u(x / i)) % mod;
            }
        }
    } return res;
}
int main()
{
    int x, y;
    scanf("%d%d",&x,&y);
    if(y % x) {
        return puts("0"), 0;
    } else {
        return printf("%lldn",(gao(y/x)%mod+mod)%mod), 0;
    }
}

————————————————————————————————————————————

E题意:没坑点，自己读下即可。
题解:可以求出连续的从 i 开始 abab… 数量 ai 。
求出问号前缀和 pre[i] 。
然后就变成dp了。
$dp[i+1]=max(dp[i+1],dp[i])$

$dp[i+m]=max(dp[i+m],pair(dp[i]+1,dp[i]+pre[m]−pre[i]))$

答案就是 $dp[n].second$ 。
max的定义是数量最大消耗问号最小(注意重载)。

复制代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1E5 + 7;
struct node
{
    int c, w;
    node():c(0),w(0){}
    node(int a,int b):c(a),w(b){}
    bool operator < (const node & x) const {
        return c < x.c || c == x.c && w > x.w;
    }
}dp[N];
int a[N], b[N], pre[N];
char s[N];
int sum(int l, int r)
{
    return pre[r] - pre[l-1];
}
int main()
{
    int n, m;
    scanf("%d%s%d",&n,s+1,&m);
    for(int i = n;i >= 1;i --) {
        if(s[i] == 'a') {
            a[i] = b[i+1] + 1;
            b[i] = 0;
        } else if(s[i] == 'b') {
            b[i] = a[i+1] + 1;
            a[i] = 0;
        } else {
            a[i] = b[i+1] + 1;
            b[i] = a[i+1] + 1;
        }
    }
    for(int i = 1;i <= n;i ++) pre[i] = pre[i-1] + (s[i] == '?');
    for(int i = 0;i < n;i ++) {
        dp[i+1] = max(dp[i+1], dp[i]);
        if(i + m <= n && a[i+1] >= m) {
            dp[i+m] = max(dp[i+m], node(dp[i].c+1, dp[i].w+sum(i+1,i+m)));
        }
    }
    printf("%dn",dp[n].w);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>

using namespace std;
const int N = 1E5 + 7;
struct node
{
    int c, w;
    node():c(0),w(0){}
    node(int a,int b):c(a),w(b){}
    bool operator < (const node & x) const {
        return c < x.c || c == x.c && w > x.w;
    }
}dp[N];
int a[N], b[N], pre[N];
char s[N];
int sum(int l, int r)
{
    return pre[r] - pre[l-1];
}
int main()
{
    int n, m;
    scanf("%d%s%d",&n,s+1,&m);
    for(int i = n;i >= 1;i --) {
        if(s[i] == 'a') {
            a[i] = b[i+1] + 1;
            b[i] = 0;
        } else if(s[i] == 'b') {
            b[i] = a[i+1] + 1;
            a[i] = 0;
        } else {
            a[i] = b[i+1] + 1;
            b[i] = a[i+1] + 1;
        }
    }
    for(int i = 1;i <= n;i ++) pre[i] = pre[i-1] + (s[i] == '?');
    for(int i = 0;i < n;i ++) {
        dp[i+1] = max(dp[i+1], dp[i]);
        if(i + m <= n && a[i+1] >= m) {
            dp[i+m] = max(dp[i+m], node(dp[i].c+1, dp[i].w+sum(i+1,i+m)));
        }
    }
    printf("%dn",dp[n].w);
    return 0;
}