题目描述

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

给一个字符串 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取模的结果。

 #include<bits/stdc++.h>

 const long long MO = 1e9+;

 const long long maxn = ;

 long long ans,inv[maxn],mp[maxn];

 int n,tt;

 char s[maxn],t[maxn];

 bool fl;

 int main()

 {

     inv[] = inv[] = ;

     for (int i=; i<maxn; i++)

         inv[i] = (long long)(MO-MO/i)*inv[MO%i]*inv[i-]%MO;

     scanf("%d",&tt);

     while (tt--)

     {

         fl = ;

         memset(mp, , sizeof mp);

         scanf("%s%s",s,t);

         for (int i=; s[i]; i++)

             mp[s[i]]++;

         for (int i=; t[i]; i++)

             mp[t[i]]--, fl = fl||(mp[t[i]]<);

         if (fl){

             printf("0\n");

             continue;

         }

         n = strlen(s)-strlen(t);

         ans = n+;

         while (n--) ans = ans*(n+)%MO;

         for (char i='a'; i<='z'; i++)

             ans = (long long)ans*inv[mp[i]]%MO;

         printf("%lld\n",ans);

     }

     return ;

 }

 inv[] = inv[] = ;

 for (int i=; i<maxn; i++)

     inv[i] = (MO-MO/i)%MO*inv[MO%i]%MO*inv[i-]%MO;

 inv[] = inv[] = ;

 for (int i=; i<maxn; i++)

     inv[i] = (MO-MO/i)%MO*inv[MO%i]%MO;

 for (int i=; i<maxn; i++) inv[i] = inv[i-]*inv[i]%MO;