挂零的网络赛 今天才发现是公式推错了 当时还以为是算法不够优化……
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<string> 7 #include<ctime> 8 #include<map> 9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<cstdlib> 13 #include<cassert> 14 #include<sstream> 15 #include<stack> 16 #include<list> 17 #include<bitset> 18 #define cl(a,b) memset(a,b,sizeof(a)) 19 #define debug(x) cerr<<#x<<"=="<<(x)<<endl 20 using namespace std; 21 typedef long long ll; 22 typedef long double ldb; 23 typedef pair<int,int> pii; 24 25 const int inf=0x3f3f3f3f; 26 const int maxn=1<<21; 27 const int p=1e9+7; 28 const double eps=1e-8; 29 const double pi=acos(-1); 30 31 int dx[8]= {0,0,1,-1,1,-1,1,-1}; 32 int dy[8]= {1,-1,0,0,-1,1,1,-1}; 33 34 ll n,m,k;//p是模 35 36 ll quick_mod(ll a, ll b) 37 { 38 ll ans = 1; 39 a %= p; 40 while(b) 41 { 42 if(b & 1) 43 { 44 ans = ans * a % p; 45 b--; 46 } 47 b >>= 1; 48 a = a * a % p; 49 } 50 return ans; 51 } 52 53 ll C(ll n, ll m) 54 { 55 if(m > n) return 0; 56 ll ans = 1; 57 for(int i=1; i<=m; i++) 58 { 59 ll a = (n + i - m) % p; 60 ll b = i % p; 61 ans = ans * (a * quick_mod(b, p-2) % p) % p; 62 } 63 return ans; 64 } 65 66 ll Lucas(ll n, ll m) 67 { 68 if(m == 0) return 1; 69 return C(n % p, m % p) * Lucas(n / p, m / p) % p; 70 } 71 72 int main() 73 { 74 int T; 75 scanf("%d", &T); 76 while(T--) 77 { 78 scanf("%lld%lld%lld", &n, &m, &k); 79 ll res = Lucas(n - m * k - 1, m - 1); 80 (res *= n) %= p; 81 res *= quick_mod(m, p - 2); 82 res %= p; 83 printf("%lld ", res); 84 } 85 return 0; 86 }