AtCoder - 3954 Painting Machines

题面在这里!

题解见注释

/*
考虑一个可以用 K ((n+1)/2 <= K < n)次染黑的方案,
那么将操作前K次的机器从小到大排序,一定是:
a1=1 < a2 < ...< ak=n-1
并且 a[i+1]-a[i] <= 2 转化模型,就是一个变量初始等于 1 ,每次操作可以 +1 或者 +2 ,
k-1 次操作之后 = n-1 的方案数. C(k-1 , n-k-1) * (k!) * ((n-k-1)!)
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int ha=1e9+7,N=1e6+5,mod=ha-1; inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;} inline int ksm(int x,int y){
int an=1;
for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
return an;
} int n,jc[N],ni[N],ans,f[N]; inline void init(){
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha;
ni[n]=ksm(jc[n],ha-2);
for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha;
} inline void solve(){
for(int k=n+1>>1;k<n;k++) f[k]=jc[k]*(ll)jc[k-1]%ha*(ll)ni[2*k-n]%ha;
for(int k=n+1>>1;k<n;k++) ADD(ans,add(f[k],ha-f[k-1])*(ll)k%ha);
} int main(){
scanf("%d",&n),init();
solve(),printf("%d\n",ans);
return 0;
}
上一篇:Python: AES加密与解密


下一篇:ae学习