Wuyanru's blog
0%

[GLR-R3] 清明

发表于 分类于 ，

神仙一般的计数题。

题目链接。

题意

现在有 个位置，第 个位置初始的时候有 单位的水。

第 个位置上的水将会跳到 的任意一个位置去，满足跳到每一个位置上的水都是非整数单位个，并且总和为 单位。

所有位置的水同时跳动，假设最终第 个位置上有 个单位的水，则这种跳动方案权值为 。

求所有本质不同方案的权值和，两种方案不同当且仅当存在 满足 跳到 上的水个数不同。

。

题解

看完题感觉一点思路都没有。

Subtask5

此部分数据保证 。也就是说第 个位置的水只可能流到 或 。

设 向 流了 单位的水，那么一个方案的权值是 。

那么考虑拆贡献，也就是说一个位置的贡献可能是 两种取值。

直接使用 表示决定完了前 个位置的 以及选哪种贡献，第 个位置不选／选 这个贡献，前面的权值和。

那么可以得到： 初始状态为 ，答案为 。

时间复杂度 。

Subtask6

此部分保证 ，也就是说水可以任意流动。

设 表示位置 的水有多少是从 来的，若 或 则 ，并且 。

那么答案就是 。

还是考虑去拆贡献，不难发现贡献相当于是在移动完水滴之后，从 里面各拿出一滴水的方案数。

那么对于一个方案，设 为，从 这一堆取出的这滴水，在移动之前来自哪一堆。

再令 ，可以发现方案数仅和 有关，并且这个方案数对于每一个 是独立的。

令 与 ，特殊的，这一部分 。

写出答案的生成函数： 那么我们就相当于要求 。

容易发现，，组合意义是把 个相同的球放入 个不同的盒子中，盒子可以空。

那么可以知道 ，那么我们要求的就是 。

注意到 是 级别的，也就是说这个组合数的值容易在 复杂度内求出来，所有组合数可以直接 预处理。

那么这部分就可以直接 dp 了，考虑从前往后决定 的取值。

设 表示当前已经确定了 的 取值，并且 ，权值总和是多少。

初始状态为 ，转移直接枚举 ，那么 。

答案即为 ，时间复杂度 。

Subtask7

此部分保证 。

还是上面那个思路，考虑进行状压 dp。

令 表示已经确定完了 的 取值， 这一段区间里面 里面的数字已经确定好了 ，剩余的未确定。

直接做的话就是枚举 里面有哪些元素，复杂度是 ，无法通过。

考虑按照类似逐位转移的顺序来做，将所有 按照 的大小分组，分别进行转移。

同一组里面，所有的 都相等，也就是说若 转移到了 ，那么知道 就可以知道转移系数。

（注意这一部分里面上面的 取值与上一个 Subtask 不同）

那么就直接从 枚举到 ，逐位进行转移即可，时间复杂度 。

Subtask9

考虑当 比较大的时候（例如 ）会有什么特殊性质。

带给我们的限制是要求 ，那么可以发现只有至多 的时候这个限制才可能会不满足。

那么如果 比较大，可能不满足限制的 就会比较少，那么会有一个新的 dp 方式。

首先进行容斥，我们先钦定 里面一部分数字不合法。

然后使用 表示当前决策完了 的所有 ，目前还有 个额外的位置没有安放。

转移的时候先枚举 ，再看一下 和 的方案就好了。

时间复杂度是 。我们将这个复杂度和 Sub7 平衡一下。

复杂度不会算，实现的时候比较一下哪种复杂度更小就用哪个就行，打表算一下就能知道 的时候复杂度在 左右。

代码

所以为啥谷上题解的 dp 都是倒着的啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=998244353;
ll f[40][40];
ll g[40][3];
ll inv[80];
ll iiv[80];
int a[40];
int n,k;
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline ll C(int a,int b)
{
    if(a<b||b<0) return 0;
    ll ans=1;
    for(int i=1;i<=b;i++) ans=ans*(a-i+1)%mod*inv[i]%mod;
    return ans;
}
inline void Add(ll &a,ll b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
namespace Sub7
{
    ll fp[20][131072];
    ll dp[131072];
    int num[131072];
    inline void mian()
    {
        dp[1]=1;
        for(int i=0;i<(2<<k);i++) num[i]=__builtin_popcount(i);
        for(int i=1;i<=n;i++)
        {
            int v=min(k+1,n-i+1),lim=1<<v,lst=1<<min(k+1,n-i+2);
            for(int j=0;j<lst;j++)
            {
                if(j&1) fp[num[j>>1]][j>>1]=dp[j];
                dp[j]=0;
            }
            for(int j=0;j<=v;j++)
            {
                for(int x=0;x<v;x++) for(int y=0;y<(1<<v);y++) if(y&(1<<x)) Add(fp[j][y],fp[j][y^(1<<x)]);
                for(int x=0;x<lim;x++) if(fp[j][x]) Add(dp[x],fp[j][x]*f[i][num[x]-j]%mod),fp[j][x]=0;
            }
        }
        printf("%lld\n",dp[1]);
    }
}
namespace Sub9
{
    ll dp[40];int ty[35];
    inline void mian()
    {

        ll ans=0;
        for(int i=0;i<(1<<(n-k-1));i++)
        {
            memset(dp,0,sizeof(dp)),dp[0]=1;
            for(int j=1;j<=n;j++) ty[j]=(i>>(n-j))&1;
            for(int j=1;j<=n;j++)
            {
                //第j个位置
                for(int x=n;x>=0;x--) if(dp[x])
                {
                    ll mem=dp[x];dp[x]=0;
                    for(int p=0;p+x<=n-j+1;p++) Add(dp[x+p],mem*iiv[p]%mod*f[j][p]%mod);
                }
                int need=0;
                if(ty[j]==0) need++;
                if(j+k+1<=n&&ty[j+k+1]) need++;
                for(int x=0;x<=n;x++)
                {
                    dp[x]=dp[x+need]*g[x+need][need]%mod;
                }
            }
            //ans is dp[0];
            if(__builtin_parity(i)) ans-=dp[0];
            else ans+=dp[0];
        }
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
}
int main()
{
    n=read(),k=read();

    ll now=1;iiv[0]=1;
    for(int i=1;i<=2*n;i++)
    {
        now=now*i%mod;
        iiv[i]=qow(now,mod-2);
        inv[i]=qow(i,mod-2);
    }

    g[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();int all=min(k+1,n-i+1);
        for(int j=0;j<=all;j++) f[i][j]=C(all-1+a[i],all+j-1);
        g[i][0]=1;g[i][1]=i,g[i][2]=i*(i-1);
    }
    ll val1=(1ll<<(n-k-1))*n*n*n;
    ll val2=(1ll<<k)*k*k*(n-k);
    if(val2<=val1) Sub7::mian();
    else Sub9::mian();
    return 0;
}