Submission #36904284

---

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 sub(int a, int b) {
	if (b == 0) return a;
	/* b が正のとき、P - b は P 未満 */
	/* b が P 未満 のとき、P - b は正 */
	return add(a, P - b);
}

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

/* [もとの文字列を何文字決めたか][操作後の文字列が何文字になったか] */
int memo[MAX][MAX];
/* もとの文字列の長さの降順の累積和 */
int memoSum[MAX][MAX];

int main(void) {
	int srcLen, destLen;
	if (scanf("%d%d", &N, &P) != 2) return 1;

	/* 操作後の文字列が N 文字未満で、操作前の文字列が N 文字に到達した */
	for (destLen = 0; destLen < N; destLen++) {
		memo[N][destLen] = 1;
		memoSum[N][destLen] = 1;
	}
	/* 操作前の文字列の長い順に求めていく */
	for (srcLen = N - 1; srcLen >= 0; srcLen--) {
		/* 操作後の文字列が N 文字以上になったら条件を満たさないので、そこまで求めればいい */
		for (destLen = 0; destLen < N; destLen++) {
			int ans = 0;
			int i;
			int delta = 2; /* 操作後の文字列の長さが増える量 */
			int deltaLast = 9; /* 増える量が delta となる最後の置く長さ */
			/* 次に同じ文字を何文字置くか、それぞれを試す */
			for (i = 1; srcLen + i <= N; ) {
				/* 操作前の文字列が N 文字になるまでで打ち切る */
				if (srcLen + deltaLast > N) deltaLast = N - srcLen;
				/* 累積和を用いて加算する */
				ans = add(ans, sub(memoSum[srcLen + i][destLen + delta],
					memoSum[srcLen + deltaLast + 1][destLen + delta]));
				/* 次の部分について求める準備をする */
				i= deltaLast + 1;
				delta++;
				deltaLast = deltaLast * 10 + 9;
			}

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

			/* 結果をメモする */
			memo[srcLen][destLen] = ans;
			/* 累積和をとる */
			memoSum[srcLen][destLen] = add(memo[srcLen][destLen], memoSum[srcLen + 1][destLen]);
		}
	}

	printf("%d\n", memo[0][0]);
	return 0;
}

Submission Info

Judge Result