Bobbie edited 1 年，8 月前
简要描述一下我程序的过程：首先构建查询数组c[j][i]，存储的信息是在i位之前（包含i）最靠近i的值为j的字符位置，每次询问分为两位数相等和两位数不等两种情况。
在不等时：遍历每个字符，遍历遇到第二位数时，然后用查询数组寻找第一位数的位置，如果第一位数前面其他数的数量 大于 需要寻找的长度-2（本身第一位数和第二位数已经占了两位了）,就从中挑选( 需要寻找的长度-2)个数，用组合数的方式计算(cal函数)
在相等时：道理也一样就是跳过第一次遇到的第二位数，然后查询计算时稍作更改
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e9+7;
char s[2020];
int c[10][2020];
int cal(int x, int y)
{
if(x-y<y) y=x-y;
long long ans=1;
for(int i=1;i<=y;i++,x--)
ans=(ans*x/i)%N;
return (int) ans;
}
int main()
{
scanf("%s",s+1);
int size=strlen(s+1);
for(int i=1;i<=size;i++)
{
int t=s[i]-'0';
for(int j=0;j<10;j++)
if(j==t) c[j][i]=i;
else c[j][i]=c[j][i-1];
}
int times;
cin>>times;
while(times--)
{
long long res=0;
int lenth;
int qqqq;
int x,y;
int cur;
cin>>lenth>>qqqq;
if(lenth>2000)
{
cout << "0" << endl;
continue;
}
x=qqqq/10,y=qqqq%10;
bool pd=false;
if(x!=y)
for(int i=1;i<=size;i++)
{
if(s[i]-'0'==y)
{
int t=i;
while(c[x][t]>=lenth-1)
{
//cout<<c[x][t]-1<<" "<<lenth-2<<endl;
res=(res+cal(c[x][t]-1,lenth-2))%N;
t=c[x][c[x][t]-1];
}
}
}
else
for(int i=1;i<=size;i++)
{
if(s[i]-'0'==y && pd)
{
int t=i;
while(c[x][c[x][t]-1]>=lenth-1)
{
//cout<<c[x][c[x][t]-1]-1<<" "<<lenth-2<<endl;
res=(res+cal(c[x][c[x][t]-1]-1,lenth-2))%N;
t=c[x][c[x][t]-1];
if(t==cur) break;
}
}
if(s[i]-'0'==y) pd=true,cur=i;
}
cout<<res<<endl;
}
return 0;
}