题目大意
给定正整数$N$，求符合下列条件的整数$X$的个数，对$998244353$取模：
- $X$是$N$位的正整数
- $X$的每一位数都在$[1,9]$之间（==0不行==）；
- $X$的相邻两位数之差的绝对值不超过$1$。
$2\le N\le 10^6$
输入格式
$N$
输出格式
输出答案。
样例
| $N$ |
输出 |
| $4$ |
$203$ |
| $2$ |
$25$ |
| $1000000$ |
$248860093$ |
分析
$$
f(i,j)=\begin{cases}
1&(i=1)\\
f(i-1,1)+f(i-1,2)&(j=1)\\
f(i-1,8)+f(i-1,9)&(j=9)\\
f(i-1,j-1)+f(i-1,j)+f(i-1,j+1)&(i>1,2\le j\le8)
\end{cases}
$$
因此，直接输出$\sum\limits_{i=1}^9f(n,i)$即可。
代码
本代码运用了滚动表的优化，当然也可以直接开$N\times9$大小的数组，但这样会导致内存占用大，不建议使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <cstdio>
#define MOD 998244353
using namespace std;
inline void mod(int& x)
{
if(x >= MOD) x -= MOD;
}
int dp[9], ldp[9];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<9; i++)
dp[i] = 1;
while(--n)
{
for(int i=0; i<9; i++)
ldp[i] = dp[i];
mod(dp[0] += dp[1]), mod(dp[8] += dp[7]);
for(int i=1; i<8; i++)
mod(dp[i] += ldp[i - 1]),
mod(dp[i] += ldp[i + 1]);
}
int ans = 0;
for(int i=0; i<9; i++)
mod(ans += dp[i]);
printf("%d\n", ans);
return 0;
}
|
题目大意
给定由A、B、C组成的字符串$S$。令$S_0=S$，$S_i=S_{i-1}$将A、B、C分别替换为BC、CA、AB的新字符串。
回答$Q$个查询，第$i$个查询的问题如下：
$1\le |S|\le 10^5$
$1\le Q\le 10^5$
$1\le t_i\le 10^{18}$
$1\le k_i\le min(10^{18},S_{t_i}$的长度$)$
输入格式
$S$
$Q$
$t_1~k_1$
$\vdots$
$t_Q~k_Q$
样例
样例输入1
1
2
3
4
5
6
|
ABC
4
0 1
1 1
1 3
1 6
|
样例输出1
样例输入2
1
2
3
4
5
6
7
|
CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665
|
样例输出2
注意小心整数溢出问题。
分析
$$
f(t,k)=\begin{cases}
0 & (t=0)\\
g(0,t) & (k=0)\\
g(f(t-1,\lfloor\frac k2\rfloor),(k\bmod2)+1) & (t>0,k>0)
\end{cases}
$$
其中$g(c,x)$为字符$c$在A,B,C,A,...这个环中$c$后面的第$x$个字符，即$g(c,x)=(c+x)\bmod3$。
因此，我们只要求出$x$在$S$的哪个字符分解后的结果中，再计算$f$即可。
答案为$\mathrm{ans}=g(f(t,(k-1)\bmod2^t),S_{\lfloor\frac {k-1}{2t}\rfloor})$。
代码
以下两种示范代码均使用非递归形式，当然也可使用递归形式。
代码1（标准）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <cstdio>
using namespace std;
char s[100005];
int main()
{
scanf("%s", s);
int q;
scanf("%d", &q);
while(q--)
{
long long t, k;
scanf("%lld%lld", &t, &k);
k --;
int x = s[t < 64? k >> t: 0] - 'A'; // 防止t太大导致RE
while(t > 0 && k > 0)
{
x = (x + int(k & 1LL) + 1) % 3;
k >>= 1LL, t --;
}
putchar((t + x) % 3 + 'A');
putchar('\n');
}
return 0;
}
|
代码2（优化）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <cstdio>
using namespace std;
char s[100005];
int main()
{
scanf("%s", s);
int q;
scanf("%d", &q);
while(q--)
{
long long t, k;
scanf("%lld%lld", &t, &k);
k --;
int c = 0;
if(t < 64)
{
c = s[k >> t] - 'A';
k &= (1LL << t) - 1LL;
}
else c = s[0] - 'A';
for(c+=t%3; k>0; k&=k-1) c ++;
putchar(c % 3 + 'A');
putchar('\n');
}
return 0;
}
|
题目大意
对于$T$个测试点，分别解决下列问题：
给定整数$N$和字符串$S$，求合法字符串$X$的个数，使其符合下列条件：
- $|X|=N$
- $X$由大写英文字母组成，是一个回文串
- 按字典序，==$X\le S$==
$1\le T\le 250000$
$1\le N\le 10^6$
$1\le \sum N\le 10^6$
$|S|=N$且由大写英文字母组成。
分析
显然，通过$X$的前$\lceil\frac N2\rceil$个字符就可以确定唯一的$X$。下面，我们以ABCDE为例：
ABCDE的前$\lceil\frac N2\rceil$个字符分别为ABC- 字典序小于
ABC的字符串有$28$个（可看作一个$26$进制数来计算）
- 判断
ABCBA是否可行，与ABCDE比较
- 可行，答案增加$1$得到$29$
因此，我们输出$29$。其他情况类似。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <cstdio>
#define maxn 1000005
#define MOD 998244353
using namespace std;
using LL = long long;
char s[maxn];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n;
scanf("%d%s", &n, s);
long long x = 0LL;
int j = n - 1 >> 1;
for(int i=0; i<=j; i++)
(x = x * 26LL + s[i] - 'A') %= MOD;
bool ok = true;
while(j >= 0)
{
if(s[j] < s[n - 1 - j]) break;
if(s[j] > s[n - 1 - j]) { ok = false; break;}
j --;
}
if(ok && ++x == MOD) x -= MOD;
printf("%lld\n", x);
}
return 0;
}
|