P4798 [CEOI2015 Day1]卡尔文球锦标赛

Mobius127 · 2021-07-28 23:11:47 · 题解

题传

谁来帮窝卡一卡常 qwq，不开 O2 过不去。。。

不难想到，每个人选择的队伍编号只能是 [1,\text{前面的}\max+\ 1]，所以我们记 f_{i, j} 为到第 i 个人，最大值为 j 的总方案数，这个递推方程式不难想出。

但关键是，对于当前状态，我们不知道它与目标状态的差别，引入新一维：f_{i, j, 0/1} 表示在之前 f_{i, j} 的定义下，前 i 位是否与目标完全匹配，0 为严格小于，1 为等于。

前驱不好找，我们考虑找它对后面的贡献。

对于下一位是 j 的，若不超过，则在该位填任意数（满足不大于 j）即可，若超过， -1 即可。

如果下一位是 j+1，若不超过直接加，否则要考虑约束条件。

Code：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define now (i&1)
#define nxt ((i+1)&1)
#define int long long 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const signed mo=1e6+7;
inline int read(){
    char ch=getchar();int x=0, f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
inline int ksm(int a, int b){
    int ret=1;
    for(; b; b>>=1, a=1ll*a*a%mo)
        if(b&1) ret=1ll*ret*a%mo;
    return ret;
}
inline int mod(int x){return (x%mo+mo)%mo;}
namespace Solution{
    const int N=1e4+5;
    const int M=1e3+5;
    int n, a[N], ans, f[2][N][2];
    signed work(){
        n=read();for(int i=1; i<=n; i++) a[i]=read();f[1][1][1]=1;
        for(int i=1; i<n; i++)
            for(int j=1; j<=i; j++)
                f[nxt][j][0]=mod(f[nxt][j][0]+1ll*f[now][j][0]*j%mo+1ll*f[now][j][1]*(a[i+1]-1)%mo),
                f[nxt][j][1]=mod(f[nxt][j][1]+(a[i+1]==j+1?0:f[now][j][1])),
                f[nxt][j+1][0]=mod(f[nxt][j+1][0]+f[now][j][0]), f[nxt][j+1][1]=mod(f[nxt][j+1][1]+(a[i+1]==j+1?f[now][j][1]:0)),
                f[now][j][0]=f[now][j][1]=0; 
        for(int i=1; i<=n; i++)
            ans=mod(ans+f[n&1][i][0]+f[n&1][i][1]);
        printf("%lld", ans);
        return 0;
    }
}
signed main(){
    Solution :: work();
    return 0;
}