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

T1 pf

听说可以动归做？
真神奇，这不是数论题么。。。

我考场搞了两个半小时搞了个容斥原理做出来了。（心好累，人家 kb 随便乱搞了一下就 93 分。。。）

首先要明白，斐波那契完全用不上，就是来装逼吓人的。。。
直接用 $i$代替 $fib[i]$就行了。。。

首先，如果不需要你每个元素都至少用一次的话：序列的第一位有 $n$种选择，第二位有 $n-1$种选择，第三位有 $n-2$中选择… 第 $m+1$位有 $n-m$种选择，第 $m+2$位依然是有 $n-m$种选择，后面的也都是这样的，所以方案数是：
$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}$

但是这样子，可能某种元素没用。。。
所以我们要排除有的元素没用的方案。

如果是有 1 个元素没用的话：序列的第一位有 $n-1$种选择，第二位有 $n-2$种选择，第三位有 $n-3$种选择，第 $m+1$位有 $n-m-1$种选择，第 $m+2$位依然是有 $n-m-1$种选择，后面的也都是这样的，所以方案数是：
$(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$种元素，选择其中的一个不选，有 $n$种选法，所以方案数一共有：
$n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$

这样拿上面那个 $n!\div {(n-m)}!\times {(n-m)}^{p-m}$再减去这个 $n!\div {(n-m-1)}!\times {(n-m-1)}^{p-m}$。。。

你就发现得到的结果比答案小了。。。

这是为什么呢？
因为你减掉了的这个 1 个元素不选的方案中，还包含了 2 个元素不选的啊！
所以我们得把 2 个元素不选的加上去。。。
然而这样你又把 3 个元素不选的多加了（本来要减去的）。。。
所以我们又要把 3 个元素不选的减去。。。
然后 4 个不选的又多减了。。。
一直这样下去，还有完吗？
当然有完——一共就 n 个元素啊！

所以我们就给出答案了。。。

$i$个元素不选的方案数显然是：
${C_n^i}\times (n-i)!\times (n-m-i)^{p-m}\div (n-m-i)!$
当 $i$为奇数时，答案减去 $i$对应的方案数；
当 $i$为偶数时，答案加上 $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

唔，概率 dp。。。
考场原地蒙圈。。。

设 $f(i,j,x)$为当前比了 $i$场，背包容量为 $j$，赢了 $x$场的概率。
$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]$

因为一共只有200场，所以背包容量>200 是没有意义的，每次容量对 200min/max 一下就行了。
还有 $0\leqslant j\leqslant 400$，当 $j>=200$时表示背包还有 $400-j$的空余容量，当 $j< 200$时表示有 $200-j$个残片没装。

代码：

---

#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

考场打了个 5 维 floyd。。。
要交的时候改成了输出 0。。。
得 10 分。。。
后来发现五维 floyd 可以拿 30。。。

思路：状压 dp
设 $f(i,s)$为从节点 $i$出发，访问状态为 $s$时的简单环个数。
状态：二进制下，$s$的第 $k$位为 1 表示节点 $k$被访问过了，为 0 表示没访问过。
为防止重复计算，我们让 $i$为状态 $s$中编号最小的节点。
然后因为从一个节点扩展，环的双向都走过了，所以答案要除以二输出。

时间 1s，最后一个点 5s。。。下面提供两个优化方法（优化后第 9 个点 0.2s，第 10 个点 1.2s，原本是第 9 个点 1.2 秒，第 10 个点 5.7 秒）。

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)$为前 $i$头牛的最小价值。
$f(i)=max\{f(j)|i-k\leqslant j\leqslant i-1\}$
用单调队列维护：$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;
}

---