1 条题解

  • 0
    @ 2024-6-12 18:07:49

    暴力部分

    n20n\leq 20,一边搜索一边判断,或者搜完判断都可以。

    k=mk=m,直接输出k!k!即可,正确性懒得证。

    k=2k=2,考虑直接状压dpi,stadp_{i,sta}表示考虑到了ii,前mm个位置分别是00还是11的方案数。

    m5m\leq 5,还是直接状压,只不过状态变成了4m4^m

    正解

    考虑这样一件事,比如你当前mm个位置对应的酒分别是1,1,2,1,3,2,3

    实际上你只需要记*,*,*,1,*,2,3就可以了,也就是只保留每种酒最后一次出现的位置。反正后续对答案的贡献都一样。

    再多想一步:其实*,*,*,1,*,2,3*,*,*,3,*,1,2后续的贡献也一样,对吧。

    所以我们直接记成0001011即可。

    dpi,stadp_{i,sta}表示考虑到ii了,当前每一种酒最后一次出现的位置是stasta的方案数。

    对于每一次转移,考虑是哪一个11被替换到最前面即可。

    初始状态可以从dpm,stadp_{m,sta}开始转移,初始状态的方案数计算见代码。

    复杂度O(n2m)O(n2^m)

    #include<bits/stdc++.h>
    #define ll long long
    #define maxn 100005
    #define mod 998244353
    using namespace std;
    int dp[maxn][1<<10];
    int n,k,m;
    basic_string<int> ok;
    void add(int &x,int y) {x=(x+y)%mod; return;}
    int cal(int sta)
    {
    	ll ret=1,num=0;
    	for (int i=0;i<m;i++)
    	{
    		if ((sta>>i)&1) {ret=ret*(k-num)%mod; num++;}
    		else ret=ret*num%mod;
    	}
    	return ret;
    }
    int main()
    {
    	cin>>n>>k>>m;
    	for (int sta=1;sta<(1<<m);sta+=2)
    	if (__builtin_popcount(sta)==k)
    	{
    		dp[m][sta]=cal(sta);
    		ok+=sta;
    	}
    	int S=(1<<m)-1;
    	for (int i=m;i<n;i++)
    	for (int j:ok)
    	if (dp[i][j])
    	{
    		//必须得搞定这个位置了 
    		if ((j>>(m-1))&1) add(dp[i+1][((j<<1)&S)|1],dp[i][j]);
    		else
    		{
    			for (int w=0;w<m;w++)
    			if ((j>>w)&1)
    				add(dp[i+1][((j^(1<<w))<<1)|1],dp[i][j]);
    		}
    	}
    	int ans=0;
    	for (int sta:ok) add(ans,dp[n][sta]);
    	cout<<ans<<endl;
    }
    
    • 1

    信息

    ID
    1424
    时间
    1000ms
    内存
    1024MiB
    难度
    8
    标签
    (无)
    递交数
    96
    已通过
    17
    上传者