题目描述
有一天，小 L 给小 G 出了这样一道题：生成一个长度为 n 的、全由小写英文字母构成的字符串，只能使用 k 种字母。要求满足：
- 字符串中相邻的两个字母不能相同。
- 必须出现恰好 k 种不同的字母。
这样的合法字符串可能有很多，小 L 让小 G 输出字典序最小的那个。
小 G 太笨啦，不会做这道题，希望你帮帮他。
输入格式
输入文件只有两个数字 n; k，含义如题。
输出格式
输出文件共一行，输出合法的字典序最小的字符串。
如果不存在任意一个合法的方案，输出 1。
样例输入
7 4
样例输出
ababacd
数据范围
对于 100% 的数据，1≤n≤105; 1≤k≤26
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std; int main() {
freopen("str.in", "r", stdin);
freopen("str.out", "w", stdout);
int n, k;
cin >> n >> k; if (k > n) {
cout << - << endl;
return ;
} if (k == ) {
if (n > )
cout << - << endl;
else
cout << "a" << endl;
} else if (k == ) {
for (int i = ; i <= n; i++)
if (i % ) putchar('a');
else putchar('b');
putchar('\n');
} else {
for (int i = ; i <= n - (k - ); i++)
if (i % ) putchar('a');
else putchar('b');
for (int i = ; i < k; i++) putchar('a' + i);
putchar('\n');
}
}
题目描述
小 G 家有一座城堡。城堡里面有 n 个房间，每个房间上都写着一个数字 pi。
小 G 拉着几个小伙伴在城堡里面玩耍，他们约定，如果某个人当前站在 i 房间里面，下一步这个人就会去 pi 房间，再下一步这个人去 ppi 。
为了增加趣味性，小 G 想重新书写每个房间的 pi，以满足：
- 如果从编号 1 到 k 中的某个房间开始，按照规则走，必须能够走到 1 号房间。特别地，如果从 1 号房间开始走，也要能够走回 1 号房间（至少走一步，如果 p1 = 1，从 1 走到 1 也算合法）。
- 如果从编号大于 k 的某个房间开始，按照规则走，一定不能走到 1 号房间。
小 G 想知道，有多少种书写 pi 的方案，可以满足要求。
输入格式
输入文件一行两个数字 n; k，含义如题。
输出格式
输出文件一个数字，表示合法的方案数。答案对 109 + 7 取模
样例输入 1
5 2
样例输出 1
54
样例输入 2
7 4
样例输出 2
1728
数据范围
对于 40% 的数据，1 ≤ n ≤ 8
对于 70% 的数据，1 ≤ n ≤ 105
对于 100% 的数据，1 ≤ n ≤ 1018; 1 ≤k ≤min(8，n)。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std; typedef long long ll;
const int mod = 1e9 + ; ll n, k;
ll ans = ; inline ll qe(ll a, ll p) {
ll ans = ;
a %= mod;
for (; p; p >>= , a = a * a % mod)
if (p & )
ans = ans * a % mod;
return ans;
} int go_loc[]; inline bool check() {
static bool vis[];
memset(vis, , sizeof(vis)); int now = ;
while (!vis[now]) {
vis[now] = true;
now = go_loc[now];
}
if (now != ) return false;
for (int i = ; i <= k; i++)
if (!vis[i]) {
static bool other_vis[];
memset(other_vis, , sizeof(other_vis));
int now = i;
while (!other_vis[now] && !vis[now]) {
other_vis[now] = true;
now = go_loc[now];
}
if (!vis[now]) return false;
}
return true;
} void dfs(int now) {
if (now == k + ) {
if (check()) ans++;
return;
}
for (int i = ; i <= k; i++) {
go_loc[now] = i;
dfs(now + );
}
} int main() {
freopen("castle.in", "r", stdin);
freopen("castle.out", "w", stdout);
cin >> n >> k;
dfs();
ans = ans * qe(n - k, n - k) % mod;
cout << ans << endl;
}
题目描述
小 G 来到了著名的 CIGOM 大厦。大厦一共有 n 层，初始的时候小 G 在第 A 层。小 G 特别想去 B 层小 M 的办公室看一看，然而因为安保原因，B 层已经被*无法进入。
但是小 G 既然来了，就想在大厦里面逛一逛。大厦里面有一部电梯，小 G 决定坐 k 次电梯。因为小 G 比较无聊，他给自己设定了这样一个规矩：假如当前他在 x 层，则他要去的下一个楼层 y 和 x 的楼层差必须要小于 x 和 B 的楼层差，即|x-y| < |x-B|。每到达一个楼层，小 G 都要记录下来其楼层号。
当小 G 转完一圈后，他也记录下了 k + 1 个楼层号（可能有重复）。小 G 现在想知道，按照他定下的规矩，一共有多少种可能的楼层号序列？
输入格式
输入文件一行，4 个数字 n，A， B， k，含义如题目所述。
输出格式
输出一个数字，表示可能的楼层号序列的数量。答案对 109 + 7 取模。
样例输入 1
5 2 4 1
样例输出 1
2
样例输入 2
5 2 4 2
样例输出 2
2
样例输入 3
5 3 4 1
样例输出 3
0
数据范围
对于 30% 的数据，2≤ n≤ 8; 1 ≤ k ≤ 8。
对于 70% 的数据，2 ≤ n 300; 1 ≤ k ≤ 300。
对于 100% 的数据，2 ≤ n ≤ 5000; 1 ≤k ≤5000; 1≤ A，B≤n; A ≠B。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long ll;
const int MAXN = ;
const int MOD = ;
int f[MAXN][MAXN] = {{}};
int n, a, b, k; inline int getnum()
{
char c; int ans = ; bool flag = false;
while ((c = getchar()) == ' ' || c == '\r' || c == '\n');
if (c == '-') flag = true; else ans = c - '';
while ((c = getchar()) >= '' && c <= '') ans = ans * + c - '';
return ans * (flag ? - : );
} inline void add(int &a, int b)
{
ll tmp = (ll)a + b;
if (tmp >= MOD) a = (int)(tmp - MOD);
else if (tmp < ) a = (int)(tmp + MOD);
else a = (int)tmp;
} int main()
{
freopen("lift.in", "r", stdin);
freopen("lift.out", "w", stdout);
n = getnum(); a = getnum(); b = getnum(); k = getnum();
if (fabs(a - b) - == ) { printf("0\n"); return ; }
for (int i = a; i <= n; i++)
f[][i] = ;
for (int step = ; step <= k; step++)
for (int i = ; i <= n; i++)
if (i == b) f[step][i] = f[step][i - ];
else
{
f[step][i] = f[step][i - ];
if (i < b)
{
int x = (b + i) / ;
if ((b + i) % == ) x--;
add(f[step][i], f[step - ][x]);
add(f[step][i], -f[step - ][i]);
add(f[step][i], f[step - ][i - ]);
}
else
{
int x = (b + i) / ;
add(f[step][i], f[step - ][n]);
add(f[step][i], -f[step - ][x]);
add(f[step][i], -f[step - ][i]);
add(f[step][i], f[step - ][i - ]);
}
}
printf("%d\n", f[k][n]);
}