//唔，这次被虐的有点惨啊／（ㄒｏㄒ）／～～

# T1 pf

$n\times (n-1)\times (n-2)\times … \times (n-m) \times {(n-m)}^{p-m-1}$

$n!\div {(n-m)}!\times {(n-m)}^{p-m}$

$(n-1)\times (n-2)\times … \times (n-m-1) \times {(n-m-1)}^{p-m-1}$

$(n-1)!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$

$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$

$i$个元素不选的方案数显然是：
${C_n^i}\times (n-i)!\times (n-m-i)^{p-m}\div (n-m-i)!$

$\{i|0\leq i< n\}$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
static const LL mod=1000000007;
LL c[1005][1005],ans,tot,n,m,p;
int main()
{
freopen("pf.in","r",stdin),freopen("pf.out","w",stdout);
for(LL i=1;i<=1000;i++)c[i][0]=c[i][i]=1,c[i][1]=i;
for(LL i=3;i<=1000;i++)
for(LL j=2;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
scanf("%lld%lld%lld",&n,&m,&p);
for(LL i=0;i<n;i++)
{
tot=c[n][i];
for(LL j=n-i;j>n-m-i;j--)tot=(tot*j)%mod;
for(LL j=1;j<=p-m;j++)tot=(tot*(n-m-i))%mod;
if(!tot)break;
if(i&1)ans=(ans-tot+mod)%mod;else ans=(ans+tot)%mod;
}
printf("%lld\n",ans);
return 0;
}


# T2 guard

$f(i,j,x)=f(i-1,j,x)\times (1.0-p[i])+f(i-1,j-a[i],x-1)\times p[i]$

#include <bits/stdc++.h>
using namespace std;
int n,l,k,arr[205];
double p[205],f[205][405][205],ans;
int main()
{
freopen("guard.in","r",stdin),freopen("guard.out","w",stdout);
scanf("%d%d%d",&n,&l,&k),k=min(k,n);
for(int i=1;i<=n;i++)scanf("%lf",&p[i]),p[i]/=100.0;
for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
f[0][k+200][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=400;j++)
for(int x=0;x<=i;x++)
f[i][j][x]=f[i-1][j][x]*(1.0-p[i])+f[i-1][max(j-arr[i],0)][x-1]*p[i];
for(int i=200;i<=400;i++)
for(int j=l;j<=n;j++)
ans+=f[n][i][j];
printf("%.6lf",ans);
return 0;
}


# T3 hamilton

1. 用 low_bit 函数计算状态 $s$中编号最小的节点——先预处理处 $log2(2^i)$的值，每次获得最小节点编号则：$log2(low\_ bit(s))$。

2. 预处理出状态 $s$中被访问的节点个数（$s$二进制下数字 1 的个数），递推实现即可

#include <bits/stdc++.h>
using namespace std;
static const int maxs=20;
typedef long long LL;
int n,m,lg[1<<maxs],cnt[1<<maxs];
bool book[maxs][maxs];
LL f[maxs][1<<maxs],ans;
int main()
{
freopen("hamilton.in","r",stdin),freopen("hamilton.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)for(int j=0;j<(1<<i);j++)cnt[j|(1<<i)]=cnt[j]+1;
for(int i=0;i<n;i++)lg[1<<i]=i;
for(int i=1,a,b;i<=m;i++)scanf("%d%d",&a,&b),a--,b--,book[a][b]=book[b][a]=1;
for(int i=0;i<n;i++)f[i][1<<i]=1;
for(int s=1;s<(1<<n);s++)
{
int i=lg[s&(-s)];
for(int j=i;j<n;j++)
if((s&(1<<j))&&f[j][s])
{
for(int k=i;k<n;k++)
{
int ns=s|(1<<k);
if(book[j][k]&&!(s&(1<<k)))
{
f[k][ns]+=f[j][s];
if(book[i][k]&&cnt[ns]>=3)ans+=f[j][s];
}
}
}
}
printf("%lld\n",ans>>1);
return 0;
}


# T4 cg

$f(i)=max\{f(j)|i-k\leqslant j\leqslant i-1\}$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;
LL n,k,arr[100005],sum,minn=LLONG_MAX,f[100005],qf,qt;
pll que[100005];
int main()
{
freopen("cg.in","r",stdin),freopen("cg.out","w",stdout);
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&arr[i]),sum+=arr[i];
f[0]=0,que[qt++]=(pll){0,0};
for(int i=1;i<=n;i++)
{
f[i]=que[qf].first+arr[i];
while(que[qt-1].first>f[i]&&qf<qt)qt--;
que[qt++]=(pll){f[i],i};
while(i-que[qf].second>k&&qf<qt)qf++;
}
for(int i=n-k;i<=n;i++)minn=min(minn,f[i]);
printf("%lld\n",sum-minn);
return 0;
}