牛客挑战赛 39 牛牛与序列隔板法容斥 dp

LINK：牛牛与序列

(牛客div1的E题怎么这么水... 还没D难.

定义一个序列合法当且仅当存在一个位置i满足 $a_i>a_,a_j<a_$且对于所有的位置i,$1 \leq a_i\leq k$

人话解释：一个合法序列每个数字都在1~k之间且有两个相邻数字是递增关系两个相邻数字是递减关系。

发现我们枚举某两个位置递增递减再进行计数会重复而且很难减掉重复方案。这个不能代表元容斥。

考虑总方案-不合法方案。发现不合法方案就两种不增,不降.

显然不增翻转一下就是不降考虑求出不增的方案数考虑从前往后放数字且数字大小递减每个数字都可以分到一些位置。

容易发现是一个隔板法所以总方案数为C(n+k-1,k-1).

值得注意的是最后要加上k 因为所有数字都相同时同时为不增和不降。

这个组合数可以O(k)计算。可以通过此题。

而题解上给了一个dp 这个dp也很显然f[i][j]表示前i个数字使用的最小数字为j的方案数。

最后答案为$\sum_^f[n][i]$ 更扯得是需要打标发现是上述的组合数再接一个数学归纳法证明。

我觉得很麻烦可能正因为如此出题人才把这道题放到E吧.

const ll MAXN=100010;

ll n,k,T;

ll ans;

inline ll ksm(ll b,ll p)

{

	ll cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b%mod;

		b=b*b%mod;p=p>>1;

	}

	return cnt;

}

signed main()

{

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

	get(T);

	while(T--)

	{

		get(n);get(k);

		ans=ksm(k,n%(mod-1))+k;

		ll cnt=1,ww=1;

		fep(n+k-1,n+1,i)cnt=cnt*i%mod,ww=ww*(i-n)%mod;

		ww=ksm(ww,mod-2);

		putl(((ans-cnt*ww%mod*2%mod)%mod+mod)%mod);

	}

	return 0;

}

巴特西

牛客挑战赛 39 牛牛与序列隔板法容斥 dp

最新文章

热门文章

巴特西

牛客挑战赛 39 牛牛与序列 隔板法 容斥 dp

最新文章

热门文章

牛客挑战赛 39 牛牛与序列隔板法容斥 dp