Submission #36903869

---

Source Code Expand

#include <stdio.h>

#define MAX 3156

int N, P;

/* a + b mod P を返す */
int add(int a, int b) {
	int ret = a + b;
	/* [0, P) の数を2個足した結果は 2*P 未満 */
	if (ret >= P) ret -= P;
	return ret;
}

/* a * b mod P を返す */
int mul(int a, int b) {
	return (int)((long long)a * b % P);
}

/* 同じ文字が len 文字連続した文字列に対して操作を行ったとき、何文字になるかを求める */
int elementLength(int len) {
	int ans = 1; /* 最初にアルファベットを1個おく */
	/* 文字数の十進表現の長さを求める */
	do {
		ans++;
		len /= 10;
	} while (len > 0);
	return ans;
}

/* [もとの文字列を何文字決めたか][操作後の文字列が何文字になったか] */
int memo[MAX][MAX];
char memoValid[MAX][MAX];

int calc(int srcLen, int destLen) {
	int ans = 0;
	int i;
	/* 操作後の文字列の長さが N 以上になったため、条件を満たさない */
	if (destLen >= N) return 0;
	/* 操作後の文字列の長さが N 未満のまま操作前の文字列が N 文字になったので、条件を満たす */
	if (srcLen >= N) return 1;
	/* メモがあるなら、その値を返す */
	if (memoValid[srcLen][destLen]) return memo[srcLen][destLen];

	/* 次に同じ文字を何文字置くか、それぞれを試す */
	for (i = 1; srcLen + i <= N; i++) {
		ans = add(ans, calc(srcLen + i, destLen + elementLength(i)));
	}

	if (srcLen == 0) {
		/* 最初は、好きな文字を選べる */
		ans = mul(ans, 26);
	} else {
		/* 前回使った文字以外の中から好きな文字を選べる */
		ans = mul(ans, 25);
	}

	/* 結果をメモして返す */
	memo[srcLen][destLen] = ans;
	memoValid[srcLen][destLen] = 1;
	return ans;
}

int main(void) {
	if (scanf("%d%d", &N, &P) != 2) return 1;
	printf("%d\n", calc(0, 0));
	return 0;
}

Submission Info

Judge Result