g consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
No two neighbouring letters of a string coincide; that is, if we represent a string as s?=?s1s2... sn, then the following inequality holds,si?≠?si?+?1(1?≤?i?
n).
Among all strings that meet points 1 and 2, the required string is lexicographically smallest. Help him find such string or state that such string doesn't exist.
String x?=?x1x2... xp is lexicographically less than string y?=?y1y2... yq, if either p?
q and x1?=?y1,?x2?=?y2,?... ,?xp?=?yp, or there is such number r (r?
p,?r?
q), that x1?=?y1,?x2?=?y2,?... ,?xr?=?yr and xr?+?1?
yr?+?1. The characters of the strings are compared by their ASCII codes.
Input A single line contains two positive integers n and k (1?≤?n?≤?106,?1?≤?k?≤?26) ― the string's length and the number of distinct letters.
Output In a single line print the required string. If there isn't such string, print "-1" (without the quotes).
Sample test(s) input 7 4
output ababacd
input 4 7
output -1
构造题。构造一个字典序最小的小写字符串，使得相邻两个字母不同，而且恰好只按顺序出现了K个字母。大概的想法就是前面一直a和b交替，后来K-2位一直沿着c，d，e放下去。
注意这道题是有
cha点的。如果K=1，显然是无解，因为相邻两个不能相同。但是当N=1时还是正确的："a'！
#include
#define PR ({puts("-1");return 0;})
using namespace std;
int n,i,m;
int main()
{
scanf("%d%d",&n,&m);
if (m==1&&n==1) {putchar('a');return 0;}
if (m>n||m==1) PR;
for (i=1;i<=n-(m-2);i++)
if (i&1) putchar('a');else putchar('b');
for (i=1;i<=m-2;i++) putchar((char)(i+98));
return 0;
}
【D】
D. Polo the Penguin and Houses time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Little penguin Polo loves his home village. The village has n houses, indexed by integers from 1 to n. Each house has a plaque containing an integer, the i-th house has a plaque containing integer pi (1?≤?pi?≤?n).
Little penguin Polo loves walking around this village. The walk looks like that. First he stands by a house number x. Then he goes to the house whose number is written on the plaque of house x (that is, to house px), then he goes to the house whose number is written on the plaque of house px (that is, to house ppx), and so on.
We know that:
- When the penguin starts walking from any house indexed from 1 to k, inclusive, he can walk to house number 1.
- When the penguin starts walking from any house indexed from k?+?1 to n, inclusive, he definitely cannot walk to house number 1.
- When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house.
You need to find the number of ways you may write the numbers on the houses' plaques so as to fulfill the three above described conditions. Print the remainder after dividing this number by 1000000007 (109?+?7).
Input The single line contains two space-separated integers n and k (1?≤?n?≤?1000,?1?≤?k?≤?min(8,?n)) ― the number of the houses and the number k from the statement.
Output In a single line print a single integer ― the answer to the problem modulo 1000000007 (109?+?7).
Sample test(s) input 5 2
output 54
input 7 4
output 1728
开始还以为是DP，然后题意看了半天。大意是有N个房子，让你给每个房子加一个“索引”P，当你到了X后，你下一次去Px。再给定一个数K，对索引有下列三个要求：
①从1号点走出去后必须能回到1号点。
②从前K号点走出去后必须能回到1号点。（为什么觉得上面一个是多余的？）
③从K+1~N号点走出去后必须不能回到1号点。
求所有索引的方案取模10^9+7的值。
对于K+1~N号点，显然和1~K是隔绝的，因此方案数是简单的计算(N-K)^(N-K)。
对于1号点，显然它可以填K种索引。
对于2~K号点，开始我束手无策。后来发现K<=8!那么只要简单的dfs一下，再验证一下即可。
最后用乘法原理把三者乘起来。
#include
#include
using namespace std; typedef long long LL; const LL P=1000000007ll; int a[10],f[10],i; LL num,ans,n,k; int work(int k,int flag) { f[k]=flag;if (k==1) return 1; if (f[a[k]]!=flag) return work(a[k]