\(\mathcal{Description}\)

给定 \(n,m,p\)，求序列 \(\{a_n\}\) 的数量，满足 \((\forall i\in[1,n])(a_i\in[1,m])\land(\forall i\in(1,n])(a_{i-1}\le a_i)\land\left(\sum_{i=1}^na_i10^{n-i}\bmod p=0\right)\)，对 \(998244353\) 取模。

\(n\le10^{18}\)，\(m\le50\)，\(p\le200\)。

\(\mathcal{Solution}\)

肯定要利用 \(10^x\) 在\(\bmod p\) 意义下存在循环节的性质来求解。考场上想到暴力扫前 \(\mathcal O(p)\) 个 DP 状态然后用倍增来求解，不过死掉了 qwq。

转化题意——因为序列单调不减，记 \(1_n=\underbrace{11\cdots1}_{n\text{个}1}\)，那么任意一种序列所对应的 \(\sum_{i=1}^na_i10^{n-i}\) 都可以由若干个 \(1_x\) 相加得到。为了保证 \(a_i\ge1\)，我们钦定一个 \(1_n\) 计入贡献。而显然 \(1_x\) 在\(\bmod p\) 意义下亦存在循环节，我们可以求出 \(c_i\) 表示有 \(c_i\) 个 \(1_x\bmod p=i~(x\in[1,n])\)。问题就转化成：有 \(p\) 类物品，第 \(i\) 类物品权值为 \(i\)，有 \(c_i\) 种，每种有无数个，求选出 \(m-1\) 个物品使得其权值和\(\bmod p=0\) 的方案数。

接下来类似背包 DP，定义 \(f(i,j,k)\) 表示决定了前 \(i\) 类物品，已选了 \(j\) 个，权值和\(\bmod p=k\) 的方案数。转移枚举第 \(i+1\) 类所选个数 \(t\)，用隔板法计算方案，有：

\[f(i+1,j+t,(k+t(i+1))\bmod p)\leftarrow f(i,j,k)\binom{c_{i+1}+t-1}{c_{i+1}-1}
\]

特别留意初始状态应为 \(f(-1,0,1_n\bmod p)=1\)，因为种类编号从 \(0\) 开始；预先钦定了一个 \(1_n\)。

复杂度 \(\mathcal O(m^2p^2)\)。

\(\mathcal{Code}\)

#include <cstdio>

typedef long long LL;

#define int LL

const int MOD = 998244353, MAXM = 50, MAXP = 200;

LL n, buc[MAXP + 5];

int m, p, visc[MAXP + 5], suf[MAXP + 5], inv[MAXM + 5];

int f[2][MAXM + 5][MAXP + 5];

inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }

inline void total ( const int fir, const int cnt ) {

	bool onc[MAXP + 5] = {};

	LL cirs = cnt - visc[fir], cirt = n - cnt + cirs + 1;

	for ( int i = fir, stp = 1; stp <= cirs; i = suf[i], ++ stp ) {

		onc[i] = true;

		buc[i] = cirt / cirs + ( stp <= cirt % cirs );

		if ( stp % cirs == cirt % cirs ) f[0][0][i] = 1;//, printf ( "!%lld\n", i );

	}

	for ( int i = 1 % p, stp = 1; !onc[i] && stp <= n; i = suf[i], ++ stp ) {

		buc[i] = 1;

		if ( n == stp ) f[0][0][i] = 1;//, printf ( "!%lld\n", i );

	}

}

signed main () {

	freopen ( "charge.in", "r", stdin );

	freopen ( "charge.out", "w", stdout );

	scanf ( "%lld %lld %lld", &n, &m, &p ), -- m;

	for ( int i = 0; i < p; ++ i ) visc[i] = -1;

	for ( int l = 1, sum = 1 % p, pwr = 10 % p; ; pwr = 10 * pwr % p, ++ l ) {

		if ( ~visc[sum] ) { total ( sum, l ); break; }

		visc[sum] = l, suf[sum] = ( sum + pwr ) % p;

		if ( l == n ) { total ( sum, l ); break; }

		sum = ( sum + pwr ) % p;

	}

	inv[1] = 1;

	for ( int i = 2; i <= m; ++ i ) {

		inv[i] = 1ll * ( MOD - MOD / i ) * inv[MOD % i] % MOD;

	}

	for ( int i = -1, sta = 0; i < p - 1; ++ i, sta ^= 1 ) {

		for ( int j = 0; j <= m; ++ j ) {

			for ( int k = 0; k < p; ++ k ) {

				f[sta ^ 1][j][k] = 0;

			}

		}

		for ( int k = 0; k < p; ++ k ) {

			for ( int t = 0; t <= m; ++ t ) {

                                // 留意枚举的顺序，本质上是f(i,j,k)向后转移，

                                // 但这里统一计算了t相等时的组合数，再一起转移。

				int c = 1;

				for ( LL u = buc[i + 1] + t - 1, v = t; v; -- u, -- v ) {

					c = 1ll * c * ( u % MOD ) % MOD * inv[v] % MOD;

				}

				for ( int j = 0; j + t <= m; ++ j ) {

					addeq ( f[sta ^ 1][j + t][( k + ( i + 1 ) * t ) % p],

						1ll * f[sta][j][k] * c % MOD );

				}

			}

		}

	}

	int ans = 0;

	for ( int i = 0; i <= m; ++ i ) addeq ( ans, f[p & 1][i][0] );

	printf ( "%lld\n", ans );

	return 0;

}

\(\mathcal{Details}\)

面向数据编程 de 了好久 bug……DP 初值什么的一定不能想当然呐。

巴特西

Solution -「LOCAL」充电

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章