【Arc102c】Stop. Otherwise

Source and Judge

Arc102c

Record

2h

Analysis

请先思考后再展开

以下做法层层递进……

方法一(WA)

因为求的是组合数,肯定至少要先n能算出完整数量
$T(n,k)={ 1:∞,2:∞ … k:∞ }中选n个$
$T(n,k)={ 0:n,1:k-1 }的全排列数量$
$T(n,k)=\frac{ (n+k-1)! }{ n! (k-1)! }$
然后考虑每个i,能得到i的二元组数量
当$i-1 \leq k$,数量为$\lceil \frac{i-1}{2} \rceil$
$otherwise$,数量为$\lceil \frac{2k-i+1}{2} \rceil$
然后我们固定前面的几个(依然是多重集),根据$(-1)^k$ 去贡献,后面乱搞

然后,手动模拟样例2发现,相同的用多次,
后面去重复,会以为多次重叠,但其实反而不应该这样
给出代码留作纪念……凉凉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll T(int n,int k) {return C(n+k-1,n);}
void main()
{
int K,n;scanf("%d%d",&K,&n);
for(int i=2;i<=2*K;i++)
{
int all=(i-1<=K)?(i-1):(2*K-i+1);
all=ceil( (double)all/2 );
ll ans=T(n,K);
for(int k=1;2*k<=n;k++)
{
ll now=C(k+all-1,k)*T(n-2*k,K)%MOD;
if(k&1) ans-=now; else ans+=now;
ans%=MOD;
}
printf("%lld\n",(ans+MOD)%MOD);
}
}

方法二(AC)

既然一定要去重,但刚才的思路,会死在【同一种多次用】上面
于是膜了发网上题解(官方看不懂……)
然后就发现其实我们是可以直接搞出合法数量而不需要取补的
(其实有可能,没办法直接求出非法数量……当初主要是觉得不好算,所以习惯性取了补以后,思维又先入为主了)

先把刚才的违法对数的种类称为tot
那么为了避免刚才的尴尬,直接枚举k表示
【在违法二元组中,只出现其中一个】(也就是其他tot-k种完全不出现)
那么每个种,相当于有了一个代表元素,方案为$2^k$
当然,这里面不一定都要真的出现
那我可以选择的数字就是oth+k个(具体是什么不重要)
这个依然可以
$$
ans=\sum_{k=0}^{tot} (-1)^k C_{tot}^k C2(oth+k,n) 2^{k}
$$

方法三(AC)

其实上面那种方法,略微有一点玄学
因为你不限制它是否出现,怎么知道在Venn图中被覆盖k次
从而使用那个$(-1)^k$ 呢?
然后我就自己再yy了一种做法,稍微改进
就连容斥都不需要了,因为按照前面的基础,
其实我完全可以把k看作一定出现至少一次(否则你枚举来干嘛,像上面那样)

$$
ans=\sum_{k=0}^{tot} C_{tot}^k C2(oth+k,n-k) 2^{k}
$$

提醒以下一个细节,要特判$oth+k=0$

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
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const ll MOD=998244353;
ll bin[4100];
ll c[4100][4100];
ll C(int n,int m) {return c[n][m];}
ll C2(int n,int m) {return C(n-1+m,n-1);}
ll solve(int i,int K,int n)
{
int tot=(i-1<=K)?(i-1):(2*K-i+1);
tot=floor( (double)tot/2 );//不再是ceil,单独考虑 i/2
int oth=K-tot*2-((i%2)==0);
ll ans=0;
for(int k=0;k<=tot and k<=n;k++)
if(oth+k>0)//debug
ans+=C(tot,k)*C2(oth+k,n-k)%MOD*bin[k]%MOD,ans%=MOD;
return (ans+MOD)%MOD;
}
void main()
{
bin[0]=1;
c[0][0]=1;
for(int i=1;i<4100;i++)
{
bin[i]=bin[i-1]*2%MOD;
c[i][0]=1;
for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
int K,n;scanf("%d%d",&K,&n);
for(int i=2;i<=2*K;i++)
if(i%2==0) printf("%lld\n",(solve(i,K,n)+solve(i,K,n-1))%MOD);//i/2的不选和选
else printf("%lld\n",solve(i,K,n));
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7deb.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%