Codeforces Round#767(Div.2) F2. Game on Sum (Hard Version)

本文主要是介绍Codeforces Round#767(Div.2) F2. Game on Sum (Hard Version)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

参考F1
仅有输入数据范围修改：
输入的第一行包含一个整数 t (1≤t≤10⁵) — 测试用例的数量。测试用例的描述如下。

每个测试用例由一行包含三个整数 n、m 和 k (1≤m≤n≤10⁶,0≤k<10⁹+7) — 回合数，Bob 必须加多少个数和 Alice 可以选择的最大数。

保证所有测试用例的 n 总和不超过 10⁶。

题解：

由F1我们知道DP状态转移方程为
DP[i][0]=0
DP[i][i]=k⋅i
并且转换DP[i][j]=(DP[i-1][j-1]+DP[i-1][j])/2
可以通过查看基本案例的贡献来优化此 DP。

如果我们在网格上绘制 DP 状态并忽略转换中的除以 2，我们可以看到状态 DP[i][i] 对状态 DP[n][m] 贡献的次数是路径数从网格中的 (i,j) 到 (n,m) 使得在每一步中，i 和 j 都增加，或者只有 j 增加，除非我们必须排除经过其他基本情况的路径。这样的路径的数量是 $\binom{n-i-1}{m-j}$ 。由于所有这些路径中的步数相同，我们可以通过最后除以 2^n-i 来解释每次转换中除以 2 的情况。

为了找到 DP[n][m] 的值，我们对 1≤i≤n 的每个基本情况 DP[i][i] 的贡献求和。

#include<bits/stdc++.h>
using namespace std;
const int p=1000000007;
inline int qow(int a,int n){int ans=1;for(a%=p;n;n>>=1){if(n&1) ans=(1ll*ans*a)%p;a=(1ll*a*a)%p;}return ans;
}
inline int inverse(int a){return qow(a,p-2);
}
int main(){int T;scanf("%d",&T);for(int pp=0;pp<T;pp++){int n,m,k;scanf("%d%d%d",&n,&m,&k);int t=inverse(qow(2,n-m));int ans=0;if(n==m){printf("%lld\n",(1ll*n*k)%p);continue;}for(int i=0;i<m;i++){ans=(ans+1ll*t*(m-i))%p;t=(1ll*t*((1ll*((p+1)/2)*((1ll*(n-m+i)*inverse(i+1))%p))%p))%p;}printf("%lld\n",(1ll*k*ans)%p);}return 0;
}