题目描述

给出一个长度为n, 由小写英文字母组成的字符串S, 求在所有由小写英文字母组成且长度为n 且恰好有k 位与S 不同的字符串中，给定字符串T 按照字典序排在第几位。

由于答案可能很大，模10^9 + 7 输出。

输入

第一行为两个整数n; k

第二行一个字符串S

第三行一个字符串T,(T即是k位与S不同的串)

输出

输出一行取模后的答案。

样例输入

4 1

abcd

bbcd

样例输出

76

数据范围

对于前30% 的数据，n<=5

对于100% 的数据，k<=n<=10^5

解法

类似于数位动态规划。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) ll(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="string.in";

const char* fout="string.out";

const ll inf=0x7fffffff;

const ll maxn=100007,mo=1000000007;

ll n,m,i,j,k,ans,bz,cnt;

char a[maxn],b[maxn];

ll c[maxn],fact[maxn];

ll qpower(ll a,ll b){

    ll c=1;

    while (b){

        if (b&1) c=c*a%mo;

        a=a*a%mo;

        b>>=1;

    }

    return c;

}

ll N(ll v){

    return qpower(v,mo-2);

}

ll C(ll u,ll v){

    return fact[v]*N(fact[u])%mo*N(fact[v-u])%mo;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d%d",&n,&m);

    scanf("%s%s",a+1,b+1);

    bz=0;

    for (i=1;i<=n;i++)

        if (a[i]<b[i]){

            bz=1;

            break;

        }

    fact[0]=1;

    for (i=1;i<=n;i++) fact[i]=fact[i-1]*i%mo;

    cnt=0;

    for (i=1;i<=n;i++){

        for (j='a';j<b[i];j++){

            if (j==a[i]) {

                if (m-cnt>n-i) continue;

                ans=(ans+(C(m-cnt,n-i))*((qpower(25,m-cnt))%mo))%mo;

            }

            else {

                if (m-cnt-1>n-i) continue;

                ans=(ans+C(m-cnt-1,n-i)*(qpower(25,m-cnt-1))%mo)%mo;

            }

        }

        if (a[i]!=b[i]) cnt++;

        if (m==cnt) break;

    }

    ans=(ans+1)%mo;

    printf("%lld",ans);

    return 0;

}

启发

类似于这一题。

往死里打。