【刷题】【cf】D1. Game on Sum (Easy Version)

搜索不行，结论推不出，就试图dp

设f[i][j]为第i轮，加入了j个元素

则Bob选择  f[i][j] <= min( f[i-1][j-1]+x , f[i-1][j]-x )

设 a=f[i-1][j-1]+x , b=f[i-1][j]-x

而A则应该最大化 f[i][j] = (a+b - |a-b| ) /2

a+b为定值，则最小化|a-b|=|2x|

由于x为所选的数，x可以为任何【0,k】中的实数，故f[i][j]=(a+b)/2

当a或者b不存在时，即为边界

j=0，则初始化为0

j=i，则初始化为i*k

后发现k可以提出来，故可以将k当作1

待2000*2000的f数组求出后，再乘以k

同时本题用到了乘法逆元知识

#include
#define int long long
using namespace std;
const int N=2001,MOD=1e9+7,INV=5e8+4;//INV(5e8+4)是2在模1e9+7意义下的乘法逆元
int f[N][N];
int n,m,k;
signed main() {
    for(register int i=1;ii) 
    {
        f[i][0]=0;
        f[i][i]=i%MOD; 
    } 
    for(register int i=2;ii)
        for(register int j=1;jj) 
            f[i][j]=(f[i-1][j-1]+f[i-1][j])%MOD*INV%MOD; 
    int T;
    scanf("%lld",&T);
    while(T--) 
    {
        scanf("%lld%lld%lld",&n,&m,&k);
        printf("%lld\n",f[n][m]*k%MOD);
    }
    return 0;
}