题目描述
有两个长度为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); }
]]>
Comments NOTHING