【数论】贝壳找房计数比赛&&祭facinv

震惊！阶乘逆元处理背后竟有如此玄机……

题目描述

贝壳找房举办了一场计数比赛，比赛题目如下。

给一个字符串 s 和字符串 t，求出 s 的所有去重全排列中 t 出现的次数。比如aab的去重全排列为aab、aba、baa。注意aaaa算出现两次aaa。

你的老大希望你帮他写一个程序作弊。

输入格式

第一行一个整数 TT，表示数据组数。

每组数据中，第一行一个字符串 ss，第二行一个字符串 tt。

数据保证 1≤T≤100, 1≤∣t∣≤∣s∣≤105，t,s 只包含小写字母。

输出格式

输出一共 TT 行，每行一个整数，表示所求答案对 10^9+7取模的结果。

样例输入

2
aab
ab
aabb
ab

样例输出

2
6

题目分析

其实就是一道挺简单的数论基础题……

但是复赛时候我想复杂了很多，一直在考虑将目标串拆成多个原串后如何去重之类的问题。

例如原串=ab，目标串=ababaa。然后设t=ab，目标串就有taaab/ttaa这两种情况，于是陷入去重无法自拔……

呃实际上冷静分析就可以发现，只用考虑拆一次的结果，那么就套上可重全排列的公式就好了。

 1 #include<bits/stdc++.h>
 2 const long long MO = 1e9+7;
 3 const long long maxn = 100035;
 4 
 5 long long ans,inv[maxn],mp[maxn];
 6 int n,tt;
 7 char s[maxn],t[maxn];
 8 bool fl;
 9 
10 int main()
11 {
12     inv[0] = inv[1] = 1;
13     for (int i=2; i<maxn; i++)
14         inv[i] = (long long)(MO-MO/i)*inv[MO%i]*inv[i-1]%MO;
15     scanf("%d",&tt);
16     while (tt--)
17     {
18         fl = 0;
19         memset(mp, 0, sizeof mp);
20         scanf("%s%s",s,t);
21         for (int i=0; s[i]; i++)
22             mp[s[i]]++;
23         for (int i=0; t[i]; i++)
24             mp[t[i]]--, fl = fl||(mp[t[i]]<0);
25         if (fl){
26             printf("0
");
27             continue;
28         }
29         n = strlen(s)-strlen(t);
30         ans = n+1;
31         while (n--) ans = ans*(n+1)%MO;
32         for (char i='a'; i<='z'; i++)
33             ans = (long long)ans*inv[mp[i]]%MO;
34         printf("%lld
",ans);
35     }
36     return 0;
37 }

然而！上面这个程序是会WA的！

在历经好长一段时间的调试之后，终于发现facinv中间溢出了……

那么大不了就改成这样嘛，反正是多一个%MO的事情

1 inv[0] = inv[1] = 1;
2 for (int i=2; i<maxn; i++)
3     inv[i] = (MO-MO/i)%MO*inv[MO%i]%MO*inv[i-1]%MO;

可是依旧WA :)

1 inv[0] = inv[1] = 1;
2 for (int i=2; i<maxn; i++)
3     inv[i] = (MO-MO/i)%MO*inv[MO%i]%MO;
4 for (int i=2; i<maxn; i++) inv[i] = inv[i-1]*inv[i]%MO;

最后只能改成上面这个样子……

行吧终于过了。

END