Codeforces Round #391 A B C D E

A. Gotta Catch Em' All!

题意

从给定的字符串中选取字符，问可构成多少个(Bulbasaur)

// 想到柯南里一些从报纸上剪汉字拼成的恐吓信_(:з」∠)_

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
using namespace std;
typedef long long LL;
int cnt[256];
char dict1[] = {'B', 'l', 'b', 's', 'r'};
char dict2[] = {'u', 'a'};
char s[maxn];
int main() {
    scanf("%s", s);
    int len = strlen(s), ans=len;
    F(i, 0, len) ++cnt[s[i]];
    F(i, 0, 5) ans = min(ans, cnt[dict1[i]]);
    F(i, 0, 2) ans = min(ans, cnt[dict2[i]]>>1);
    printf("%d
", ans);
    return 0;
}

B. Bash's Big Day

题意

从(n)个数中挑尽可能多的数使得它们的(gcdgt 1)

思路

法一

将每个数质因子分解

法二

对于每个质数，枚举其倍数

注意：特判一个数的情况

Code

Ver. 1: 93ms

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
using namespace std;
typedef long long LL;
int cnt[maxn];
void divide(int x) {
    for (int i = 2; ; ++i) {
        if (i*i>x) break;
        if (x%i==0) {
            ++cnt[i];
            while (x%i==0) x /= i;
        }
    }
    if (x>1) ++cnt[x];
}
int main() {
    int n, x, ans=0;
    scanf("%d", &n);
    F(i, 0, n) {
        scanf("%d", &x);
        divide(x);
    }
    F2(i, 2, maxn-10) ans = max(ans, cnt[i]);
    printf("%d
", ans?ans:1);
    return 0;
}

Ver. 2: 31ms

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100000
using namespace std;
typedef long long LL;
int num[maxn+10], cnt[maxn+10], prime[maxn], tot;
bool vis[maxn+10];
void work(int x) {
    for (int i = 1; ; ++i) {
        if (i*x>maxn) break;
        cnt[x] += num[i*x];
    }
}
void init() {
    F2(i, 2, maxn) {
        if (!vis[i]) prime[tot++] = i;
        work(i);
        F(j, 0, tot) {
            if (i*prime[j]>maxn) break;
            vis[i*prime[j]]=true;
            if (i%prime[j]==0) break;
        }
    }
}
int main() {
    int n, x, ans=0;
    scanf("%d", &n);
    F(i, 0, n) {
        scanf("%d", &x);
        ++num[x];
    }
    init();
    F2(i, 0, maxn) ans = max(ans, cnt[i]);
    printf("%d
", ans?ans:1);
    return 0;
}

C. Felicity is Coming!

题意

有(n)种动物，(m)个山洞，每个山洞中有(g_i)个动物（种类可重复）。

(f)为一个双射，(f(x)=y)即将动物(x)变成动物(y).

求有多少满足条件的(f)，使得变化之后每个山洞中的动物分布与之前完全相同。

思路

即找对于动物来说，有多少个等价类，每个等价类中可以全排列。

怎么找有多少个等价类呢？

动物(x)与动物(y)等价，当且仅当它们在每个山洞中的出现次数都相同。

因此，对每个动物开一个(vector)，表示它们在哪些山洞中出现，出现多次则记录多次。

则，(xleftrightarrow yiff v[x]==v[y])

将(v)排序即可

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 1000010
using namespace std;
typedef long long LL;
int n, m, x, y;
LL f[maxn];
vector<int> v[maxn];
const LL mod=1e9+7;
void init() {
    f[0] = 1;
    F2(i, 1, m) f[i] = f[i-1]*i%mod;
}
int main() {
    scanf("%d%d", &n,&m);
    F(i, 0, n) {
        scanf("%d", &x);
        F(j, 0, x) {
            scanf("%d", &y);
            v[y].push_back(i);
        }
    }
    init();
    sort(v+1, v+1+m);
    int cnt=1; LL ans=1;
    F2(i, 2, m) {
        if (v[i]==v[i-1]) ++cnt;
        else {
            (ans *= f[cnt]) %= mod;
            cnt=1;
        }
    }
    (ans *= f[cnt]) %= mod;
    printf("%I64d
", ans);
    return 0;
}

D. Felicity's Big Secret Revealed

题意

将一个长度为(n)的(01)串(s)进行分割，对于(s_1|s_2|cdots|s_{k-1}|s_{k})，其中有效的数字为(s_2,s_3,cdots,s_{k-1})，设其中的最大数为(m). 我们称一个分割为有效的，当且仅当(s_2,s_3,cdots,s_{k-1})连续地构成(1-m)的所有数（可重复）。

问有多少个有效的分割。

思路

参考：http://www.cnblogs.com/widsom/p/7417983.html

因为(nleq 75)，而1(1 bits) + 2(2 bits) + 4(3 bits) + 8(4 bits) + 5*(5 bits) = 74 bits，故最大数不会超过(20)，故进行状压(dp).

状态(state)：第(i)位为(1)当且仅当集合中有该数(i)

(dp[i][j])表示最后一刀切在(i)之前，得到的集合状态为(state)的情况总数。

至于有效的分割怎么处理呢？最后统计答案时直接统计(state)为(2)的幂次(-1)的情况即可，处理中途不用管（也无法管）。

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 80
#define maxl 1100000
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
int num[maxn][maxn], n, dp[maxn][maxl];
char s[maxn];
void init() {
    F(i, 0, n) {
        int x=0;
        F(j, i, n) {
            num[i][j] = ((x<<=1) += s[j]-'0');
        }
    }
}
int main() {
    scanf("%d%s", &n, s);
    init();
    int lim=(1<<20)-1;
    F2(i, 0, n) {
        dp[i][0] = 1;
        F(j, 0, lim) {
            if (!dp[i][j]) continue;
            F2(k, i+1, n) {
                if (num[i][k-1]>20) break;
                if (!num[i][k-1]) continue;
                (dp[k][j|(1<<num[i][k-1]-1)] += dp[i][j]) %= mod;
            }
        }
    }
    int ans=0;
    F2(i, 0, n) {
        F2(j, 1, 20) (ans += dp[i][(1<<j)-1]) %= mod;
    }
    printf("%d", ans);
    return 0;
}

E. Bash Plays with Functions

题意

(f_0(n))：有序对((u,v))的个数，满足(u*v=n)且(gcd(u,v)=1)
(f_{r+1}(n)=sum_{u*v=n}frac{f_r(u)+f_r(v)}{2})

给若干组询问(r,n)，求(f_r(n))

思路

参考：http://www.cnblogs.com/candy99/p/6284051.html

首先，(f_0(n))是什么？
记(n=p_1^{alpha_1}*p_2^{alpha_2}*cdots*p_k^{alpha_k})，则(u,v)的选取必然不能有相同的因子，所以情况必然是，(u)选择了一部分质数的所有次数，而(v)自然就选择了其他所有质数的所有次数。
故(f_0(n)=2^k).

显然，(f_{r+1}(n)=sum_{u*v=n}frac{f_r(u)+f_r(v)}{2}=sum_{u|n}f_r(u)).
因为(f_0)为积性函数，所以(f_r)为积性函数，所以$$f_r(n)=f_r(p_1^{{alpha_1}*p_2}{alpha_2}cdotsp_k^{{alpha_k})=f_r(p_1}{alpha_1})*f_r(p_2^{{alpha_2})*cdots*f_r(p_k}{alpha_k})$$
故只要求(f_r({p^alpha}))即可。

[f_r({p^alpha})=f_r(1)+f_r(p)+f_r(p^2)+cdots+f_r(p^alpha) ]

注意到，(f_0(p^alpha)=2)与(p)无关，所以可用(dp[r][alpha])表示(f_r(p_alpha))，(dp[r])为(dp[r-1])的前缀和，预处理出即可。

此外，线性筛时预处理出每个数的最小质因子，即可省得对每个(n)枚举因子。

Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 1000000
#define maxk 20
int dp[maxn+10][maxk+1], lp[maxn+10], prime[maxn], tot;
bool vis[maxn+10];
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
void init() {
    F2(i, 2, maxn) {
        if (!vis[i]) {
            prime[tot++] = i;
            lp[i] = i;
        }
        F(j, 0, tot) {
            if (i*prime[j]>maxn) break;
            vis[i*prime[j]] = true;
            lp[i*prime[j]] = prime[j];
            if (i%prime[j]==0) break;
        }
    }
    F2(i, 1, maxk) dp[0][i] = 2;
    F2(i, 1, maxn) {
        dp[i][0] = 1;
        F2(j, 1, maxk) dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod;
    }
}
LL calc(int n, int r) {
    LL ans=1;
    while (n>1) {
        int pr = lp[n], cnt=0;
        while (n % pr==0) ++cnt, n/=pr;
        (ans *= dp[r][cnt]) %= mod;
    }
    return ans;
}
int main() {
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, r;
        scanf("%d%d", &r,&n);
        printf("%I64d
", calc(n, r));
    }
    return 0;
}