题目

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

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

分析

我们从小到大枚举i，

假设1_{i-1位都是等于T的1}i-1位，那么第i位就要小于T[i]，

然后在保证不用的个数等于k的情况下，i+1~n位就可以随便选。

细节很多，小心处理。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const long long mo=1000000007;

const int N=100005;

using namespace std;

long long k,n,a[N],d[N],jc[N],ny[N],ans=1;

bool q;

char s2[N],s1[N];

long long mi(long long x,long long y)

{

	long long sum=1;

	while(y)

	{

		if(y&1) sum=sum*x%mo;

		x=x*x%mo;

		y/=2;

	}

	return sum;

}

long long c(int x,int y)

{

	return jc[x]*ny[y]%mo*ny[x-y]%mo;

}

int pre()

{

	jc[0]=1;

	for(int i=1;i<=N;i++)

	{

		jc[i]=jc[i-1]*i%mo;

		ny[i]=mi(jc[i],mo-2);

	}

	ny[0]=ny[1];

	d[0]=1;

	for(int i=1;i<=N;i++) d[i]=d[i-1]*25%mo;

}

int main()

{

	pre();

	scanf("%lld%lld",&n,&k);

	scanf("%s",s1+1);

	scanf("%s",s2+1);

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

	{

		a[i]=a[i-1];

		if(s1[i]!=s2[i]) a[i]++;

	}

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

		if(s1[i-1]==s2[i-1])

	q=true;

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

	{

		if(s1[i]==s2[i])

		{

			(ans+=(s2[i]-'a')*d[k-1]%mo*c(n-i,k-1)%mo)%mo;

		}

		else

		if(s1[i]<s2[i])

		{

			(ans+=((s2[i]-'a'-1)*d[k-1]%mo*c(n-i,k-1)%mo)%mo)%mo;

			if(k<=n-i) ans=(ans+d[k]*c(n-i,k)%mo)%mo;

			k--;

		}

		else

		if(s2[i]<s1[i])

		{

			(ans+=(s2[i]-'a')*d[k-1]%mo*c(n-i,k-1)%mo)%mo;

			k--;

		}

	}

	cout<<ans%mo<<endl;

}

巴特西

【NOIP2016提高A组五校联考2】string

题目

分析

最新文章

热门文章