[关闭]
@ysner 2018-07-29T20:11:03.000000Z 字数 1583 阅读 2138

[AtCoder3954]Painting Machines

DP 计数


题面

个物品和台机器,第台机器会为第个物品染色。设有个方案完成全部染色需动用台机器,则询问

解析

一道有一定思考难度的计数题。
我一开始想的是,可以枚举,且染色方案数决定于前台机器和后台机器的排列方案。
但这样会出现重复计数,因方案中会包含到染色提前完成的情况。
或许可以用容斥?然而我手玩过不了样例。

于是换一种思路:
最多台机器即完成染色的方案数为。(等价于“最多次完成染色”)
则恰好台的方案数为

如何计算
表示过程中动用机器、编号间隔为的次数,表示间隔为的次数。
显然第台(最后一台)机器必须动用。
则有
可解得

次动用中,间隔可任意放置,则对答案有的贡献。
然后,摆放间隔生成的排列又可打乱顺序,有的贡献。
后面还剩台机器可打乱顺序,可产生的贡献。
综上,

于是统计答案即可。预处理逆元和阶乘后复杂度为

Update:记得线性求逆元公式

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=1e6+100;
  17. ll n,x,jc[N],p,ans,Need,f[N],inv[N];
  18. il ll gi()
  19. {
  20. re ll x=0,t=1;
  21. re char ch=getchar();
  22. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  23. if(ch=='-') t=-1,ch=getchar();
  24. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  25. return x*t;
  26. }
  27. il ll C(re ll x,re ll y)
  28. {
  29. return jc[y]*inv[y-x]%mod*inv[x]%mod;
  30. }
  31. int main()
  32. {
  33. n=gi();Need=(n+1)/2;
  34. jc[0]=inv[0]=inv[1]=1;
  35. fp(i,2,n) inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;//printf("%lld ",inv[i]);
  36. fp(i,1,n) jc[i]=jc[i-1]*i%mod;
  37. fp(i,2,n) inv[i]=inv[i]*inv[i-1]%mod;
  38. fp(i,Need,n-1) f[i]=C(n-i-1,i-1)*jc[i]%mod*jc[n-i-1]%mod;
  39. fq(i,n-1,Need) f[i]=(f[i]-f[i-1]+mod)%mod;
  40. fp(i,Need,n-1) (ans+=(f[i]*i%mod))%=mod;
  41. printf("%lld\n",ans);
  42. return 0;
  43. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注