Codeforces 666C Codewords

题意

已知一个字符串 $s$ ，有 $m$ 个询问需要你回答。

对于每个询问，有两种可能性：

1型：给你另外一个字符串 $s'$ ，然后令 $s = s'$ 。（即用新串更新当前的 $s$ ）
2型：给你一个整数 $n$ ，你要回答：可以构造多少种不同的长度为 $n$ 的字符串 $p$ ，使得字符串 $s$ 是字符串 $p$ 的一个子序列，只考虑英文小写字母.

进一步解释：

子序列：假如有一个字符串 $a$ ，我们去掉其中的一些字母（只能“去掉”，而不能交换字母的位置），得到另外一个串 $b$ ，我们把 $b$ 称为 $a$ 的子序列。
举个例子： $"hhhl"$ 可以是 $"hahaschool"$ 的子序列， $"sik"$ 可以是 $"suika"$ 的子序列。

思路

首先，你需要注意到其实字符串 $s$ 的内容并不重要，影响答案的是字符串 $s$ 的长度。

我们来考虑这样的一种思路：

假设我们构造的串是 $p$ ， $s$ 是 $p$ 的子序列，我们设定： $s$ 在 $p$ 中的出现位置必须是字典序最小的。直白一点的说法： $s$ 是 $p$ 删除一些字母得到的，我们强制删除字母的时候，在连续相同的一段字母中，必须从右往左删。

举两个例子方便理解这种想法：

$s = "hahl" p = "hahaschool"$ ， $"hahl"$ 在 $"hahaschool"$ 中的对应位置必须是1、2、3、10（下标从1开始）。

$s = "abad" p = "aaabbbaaaddd"$ ， $"abad"$ 在 $"aaabbbaaaddd"$ 中的对应位置必须是1、4、7、10（下标从1开始）。

有了这种想法我们就可以把s在固定的p中的对应位置关系唯一地确定下来。同时我们得到了这样的结论：

假设s的每一位在p中对应的位置为 $p_i$ ，字符串s的内容是 $s_i$ ，那么 $s_{k+1}$ 一定不会出现在p的第 $p_k$ 位到 $p_{k+1}-1$ 位，因为如果不这样的话， $s$ 在 $p$ 中的出现位置就不是“字典序最小”的了。

有了这个结论，我们就有了初步的想法，我们首先选择 $s$ 在 $p$ 中的出现位置，这个很简单，就是 $\binom{n}{|s|}$ （其中n是要构造的p的长度，|s|是s的长度），接下来，对于每种s在p中出现位置的分布，在第 $p_{|s|}$ 位之前的未填充空位，都可以填入25种字母（参见我们刚才得到的结论），在之后的空位，都可以任意填入26种字母。

这样，如果我们枚举s在p中出现的最后位置 $p_{|s|}$ （下面用k表示），我们就可以算出答案，使用下面这个式子：

$ans=\sum_{k=|s|}^{n}\binom{k-1}{|s|-1}25^{k-|s|}26^{n-k}$

很显然如果直接拿这个式子出答案是 $O(n^2)$ 的，不满足时间限制，我们要想些办法。

观察一下上面的式子我们可以发现，可以提出 $26^n$ 这一项，这样对于相同的 $|s|$ ，不同的n的询问，我们只需要做一次 $O(n)$ 的计算就可以全数回答。这提醒我们离线处理询问：把所有询问按照|s|为第一基准，n 为第二基准进行排序，依序处理，再按出现顺序排序，依序输出。

这样做是可行的，因为 $|s|$ 最多有 $\sqrt{n}$ 种（考虑极端情况： ${|s|}_1 = 1$ , ${|s|}_2 = 2$ , ${|s|}_3 = 3$ ,…，根据等差数列求和公式，项数最多只能到 $\sqrt{100000}$ ），对于每种不同的 $|s|$ 都要做一个 $O(n)$ 的处理，所以总复杂度为 $O(n\sqrt{n})$ ，符合题目限制。

至此本题圆满解决。

实现

#define REP(i,t) for(int i = 0;i < t; i++)
#define REP_1(i,t) for(int i = 1;i <= t; i++)
#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)
#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])
#define ADHOC_CIN(typ,name) typ name;cin >> name;

using namespace std;

typedef long long LL;

int n;
string cur;

const int MAXN = 100005, MODER = 1000000007;
LL fac[MAXN],fac_inv[MAXN];
LL fac26[MAXN],fac25[MAXN];
LL fac26_inv[MAXN],fac25_inv[MAXN];
LL get_mod(LL a){
    if(a >= MODER || a < 0) a %= MODER;
    if(a < 0) a += MODER;
    return a;
}

LL mul_mod(LL a,LL b){
    return get_mod(get_mod(a)*get_mod(b));
}

LL pow_mod(LL a,LL p){
    LL ret = 1;
    while (p) {
        if(p&1) ret = mul_mod(ret, a);
        a = mul_mod(a, a);
        p >>= 1;
    }
    return ret;
}

LL sum_mod(LL a,LL b){
    return get_mod(get_mod(a) + get_mod(b));
}

LL inv_mod(LL a){
    return pow_mod(a, MODER-2);
}

void prep(){
    fac[0] = fac_inv[0] = fac26[0] = fac25[0] = fac26_inv[0] = fac25_inv[0] =  1;
    REP_1(i, MAXN-1){
        fac[i] = mul_mod(fac[i-1], i);
        fac_inv[i] = mul_mod(fac_inv[i-1], inv_mod(i));
        fac26[i] = mul_mod(fac26[i-1], 26);
        fac25[i] = mul_mod(fac25[i-1], 25);
        fac26_inv[i] = mul_mod(fac26_inv[i-1], inv_mod(26));
        fac25_inv[i] = mul_mod(fac25_inv[i-1], inv_mod(25));
    }
}

LL C(LL n,LL r){
    return mul_mod(fac[n], mul_mod(fac_inv[r], fac_inv[n-r]));
}

struct Query{
    int id,len,qrn;
    LL res;
} query[MAXN];

bool cmp_qrn(const Query &a,const Query &b){
    if(a.qrn == b.qrn) return a.len < b.len;
    return a.qrn < b.qrn;
}

bool cmp_id(const Query &a,const Query &b){
    return a.id < b.id;
}

int tot = 0;

void solve(){
    sort(query, query+tot, cmp_qrn);
    int cqrn = 0,ccur = 0;
    LL cval = 0;
    REP(i,tot){
        if(query[i].len < query[i].qrn){
            query[i].res = 0;
            continue;
        }
        if(query[i].qrn != cqrn){
            ccur = cqrn = query[i].qrn;
            ccur--;
            cval = 0;
        }
        while(ccur < query[i].len){
            ccur++;
            cval = sum_mod(cval, mul_mod(mul_mod(mul_mod(fac25[ccur], fac25_inv[cqrn]), fac26_inv[ccur]), C(ccur-1,cqrn-1)));
        }
        query[i].res = mul_mod(cval, fac26[query[i].len]);
    }

    sort(query, query+tot, cmp_id);
    REP(i, tot){
        cout << query[i].res << endl;
    }
}

int main(int argc, const char * argv[]){
    prep();
    cin >> n >> cur;
    REP_1(i, n){
        ADHOC_CIN(int, op);
        if(op == 1){
            cin >> cur;
        }else{
            ADHOC_CIN(int, a);
            query[tot] = {tot++,a,(int)cur.size(),0};
        }
    }
    solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#define REP(i,t) for(int i = 0;i < t; i++)

#define REP_1(i,t) for(int i = 1;i <= t; i++)

#define CASE_LOOP int ___;scanf(" %d",&___);for(int __ = 1; __ <= ___; __++)

#define FOR_EDGE(i,u) for (int i = head[u]; i; i = nxt[i])

#define ADHOC_CIN(typ,name) typ name;cin >> name;

using namespace std;

typedef long long LL;

int n;

string cur;

const int MAXN = 100005, MODER = 1000000007;

LL fac[MAXN],fac_inv[MAXN];

LL fac26[MAXN],fac25[MAXN];

LL fac26_inv[MAXN],fac25_inv[MAXN];

LL get_mod(LL a){

if(a >= MODER || a < 0) a %= MODER;

if(a < 0) a += MODER;

return a;

}

LL mul_mod(LL a,LL b){

return get_mod(get_mod(a)*get_mod(b));

}

LL pow_mod(LL a,LL p){

LL ret = 1;

while (p) {

if(p&1) ret = mul_mod(ret, a);

a = mul_mod(a, a);

p >>= 1;

}

return ret;

}

LL sum_mod(LL a,LL b){

return get_mod(get_mod(a) + get_mod(b));

}

LL inv_mod(LL a){

return pow_mod(a, MODER-2);

}

void prep(){

fac[0] = fac_inv[0] = fac26[0] = fac25[0] = fac26_inv[0] = fac25_inv[0] = 1;

REP_1(i, MAXN-1){

fac[i] = mul_mod(fac[i-1], i);

fac_inv[i] = mul_mod(fac_inv[i-1], inv_mod(i));

fac26[i] = mul_mod(fac26[i-1], 26);

fac25[i] = mul_mod(fac25[i-1], 25);

fac26_inv[i] = mul_mod(fac26_inv[i-1], inv_mod(26));

fac25_inv[i] = mul_mod(fac25_inv[i-1], inv_mod(25));

}

LL C(LL n,LL r){

return mul_mod(fac[n], mul_mod(fac_inv[r], fac_inv[n-r]));

}

struct Query{

int id,len,qrn;

LL res;

} query[MAXN];

bool cmp_qrn(const Query &a,const Query &b){

if(a.qrn == b.qrn) return a.len < b.len;

return a.qrn < b.qrn;

}

bool cmp_id(const Query &a,const Query &b){

return a.id < b.id;

}

int tot = 0;

void solve(){

sort(query, query+tot, cmp_qrn);

int cqrn = 0,ccur = 0;

LL cval = 0;

REP(i,tot){

if(query[i].len < query[i].qrn){

query[i].res = 0;

continue;

}

if(query[i].qrn != cqrn){

ccur = cqrn = query[i].qrn;

ccur--;

cval = 0;

}

while(ccur < query[i].len){

ccur++;

cval = sum_mod(cval, mul_mod(mul_mod(mul_mod(fac25[ccur], fac25_inv[cqrn]), fac26_inv[ccur]), C(ccur-1,cqrn-1)));

}

query[i].res = mul_mod(cval, fac26[query[i].len]);

}

sort(query, query+tot, cmp_id);

REP(i, tot){

cout << query[i].res << endl;

}

int main(int argc, const char * argv[]){

prep();

cin >> n >> cur;

REP_1(i, n){

ADHOC_CIN(int, op);

if(op == 1){

cin >> cur;

}else{

ADHOC_CIN(int, a);

query[tot] = {tot++,a,(int)cur.size(),0};

}

solve();

return 0;

}

Codeforces 666C Codewords

题意

思路

实现

Related

hahaschool

Leave a Reply Cancel reply

题意

思路

实现

Related

hahaschool

You May Also Like

最短路教程

Codeforces 295D Greg and Caves

后缀数组

Leave a Reply Cancel reply