SSL 2694_字符串_数论

发布于 2017-08-15  861 次阅读


题目描述

有两个长度为n且仅由小写字母组成的字符串S,T,满足S和T恰好有k位不同。问在所有恰好与S有k位不同的字符串中,T按照字典序排在第几位。由于答案可能很大,模10^9+7输出。


 

思路

具体算法解释可见 学霸 的博客

http://blog.csdn.net/zhanghaoxian1/article/details/77199008


 

我们就从第一位开始统计: 
首先字符串的第一位肯定不能大于T的第一位 
那么如果S的第一位比T的第一位要小,那么第一位对答案的贡献就是 
C(n-1,m-1)25^(m-1)(T[1]-‘a’-1)+C(n-1,m)*25^m然后要m– 
如果S的第一位比T的第一位要大,那么第一位对答案的贡献就是C(n-1,m-1)25^(m-1)(T[1]-‘a’)然后要m– 
如果S的第一位等于T的第一位,那么对答案的贡献就是C(n-1,m-1)25^(m-1)(T[1]-‘a’) 
然后往下一位一样的接着处理就好了。 
至于组合数取模:a/b%c=a*b^(c-2)%c;


 

此题中要我们疯狂的求组合数$C_m^n = \frac{m!}{n!(m-n)!}$ 我们将这个设为 $\frac{a}{b}$

但是我们直接求会爆,且显然 $\frac{a \mod p}{b \mod p} != \frac{a}{b} \mod p$

所以我们就要用逆元来将其变为乘法, 我们知道费马小定理为若p为质数 $a^p-1\equiv 1\pmod{p}$

然后除以b可以变为乘$b^{-1}$那么我们将其变为$b^{-1} * b = 1$我们知道1和大于1的数取模肯定为1

我们要求的数因为是肯定要取模的,所以我们可以将这个表示为$1 \mod p = b ^{p - 1} \mod p = b^{-1} * b$ 

我们要取的数是$b^{-1}$ 所以对应的我们的$b ^{p - 1}$ 要多除一个b变为 $b^{p-2}$

然后我们就可以用快速幂求解并在其中取模,然后就可以愉快的做这题了


 

#include 
#include 
#include 
#include 
using namespace std;
#define p 1000000007
#define maxn 200000
#define LL long long
char s1[maxn], s2[maxn];
LL n, k, f[maxn], l[maxn], g[maxn];
LL pow(LL a, LL b)
{
    LL r = 1, base = a;
    while (b)
    {
        if (b&1) r *= base;
        r %= p;
        base *= base;
        base %= p;
        b >>= 1;
    }
    return r;
}
LL c(LL a, LL b)
{
    return f[a] * l[a - b] % p * l[b] % p;
}
int main()
{
    scanf("%d%d", &n, &k);
    cin >> s1 + 1 >> s2 + 1;
    f[0] = g[0] = l[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] * i % p;
        g[i] = g[i - 1] * 25 % p;
        l[i] = pow(f[i], p - 2);
    }
    LL ans = 1;
    for (int i = 1; i <= n; i++)
    {
        if (s1[i] == s2[i])
        {
            ans += (s2[i] - 'a') * g[k - 1] % p * c(n - i, k - 1) % p;
            ans %= p;
        }
        if (s1[i] > s2[i])
        {
            ans += (s2[i] - 'a') * g[k - 1] % p * c(n - i, k - 1) % p;
            ans %= p;
            k--;
        }
        if (s1[i] < s2[i])
        {
            ans += (s2[i] - 'a' - 1) * g[k - 1] % p * c(n - i, k - 1) % p;
            ans %= p;
            if (n - i >= k) ans += c(n - i, k) % p * g[k] % p;
            ans %= p;
            k--;
        }
    }
    printf("%lld\n", ans);
}

 


 

]]>