C. 她的名字
单测试点时限: 4.0 秒
内存限制: 512 MB
“他走过一个又一个星球,
却始终放不下对她的思念。“
”深情终究是一趟孤独的旅程,
她是他永远的牵绊。”
我们每个人心中都有一只小狐狸。我们渴望被自己喜欢的人驯服。
爱情是彼此之间至为甜蜜的臣服。我们都是傻痴痴的小狐狸,徒具一副精明的外表。
就像你走到哪都挂念着她,想把她写进自己的歌里,成为你们共同的记忆。
你想从她全部由数字构成的名字里取出其中的 N 个数字,维持原来的顺序,组成结尾为数字 XY 的新词。
你自然希望自己的歌能够很长很长,歌词的每一句都能饱含甜蜜。
所以你想知道,她的名字能够组成多少个长度为 N 且结尾为数字 XY 的新词(如果从她名字中取出的任意一个数字位置不同,两个词就被认为是不同的)。
输入
第一行包含一个由数字构成的字符串 S (1≤|S|≤2 000)。
第二行包含一个整数 Q (1≤Q≤5⋅105),表示需要选择的不同结尾数量。
接下来的 Q 行,每行包含了一个整数 N (1≤N≤5⋅105) 和两个数字 XY,用空格隔开,表示需要选择的歌词的长度和结尾。
输出
对于每一个询问,输出一个整数,表示答案。
答案可能会很大,你只需要输出对于 109+7 取模后的结果。
样例
input
312121
4
2 21
3 31
4 22
3 22
output
3
0
1
2
提示
样例中第一个询问:312121, 312121, 312121.
第二个询问:无。
第三个询问:312121.
题意:略;
题解:自己没写出来,听说需要预处理,不预处理会超时,后来补提,感觉暴力真好:详细解释看代码:
#include <iostream>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int MAX = 2018;
ll c[MAX][MAX];
ll ans[MAX][MAX];
void init(){//组合数,公式就不说了
c[0][0]=1;
for (int i = 1; i <= 2000;i++){
c[i][0]=1;
for (int j = 1; j <= i;j++){
if(j<=i/2) c[i][j]=(c[i-1][j-1]%mod+c[i-1][j]%mod)%mod;
else c[i][j]=c[i][i-j];
}
}
}
int main(){
init();
string s;
cin >> s;
int len=s.size();
for (int i = 0; i <= 9;i++){//预处理
for (int j = 0; j <= 9;j++){
int sum=0;//统计i后面有几个j
for (int k = len-1; k >= 0;k--){
for (int r = 2; r <= k+2;r++)
if(s[k]==i+'0'&&sum) ans[r][i*10+j]=(ans[r][i*10+j]%mod+c[k][r-2]%mod*sum%mod)%mod;
if(s[k]==j+'0') sum++;
}
}
}
int q;
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
if(x>len||x<2) printf("0\n");//大于字符串长度,和小于2直接不存在
else printf("%d\n",ans[x][y]);
}
return 0;
}