关于实现
查看原帖
关于实现
895690
gghack_Nythix楼主2024/8/5 10:46

为什么以下代码必须要将 jj 倒着枚举?

#include<iostream>
#define int long long
#define cput cout
using namespace std;
const int mod = 1e9 + 7;
int n,m,c,aU;
int invfac[200005],fac[200005],F[200005];
inline int C(int n,int m){return ((fac[n] * invfac[m] % mod) % mod * invfac[n - m] % mod) % mod;}
inline int ksm(int a,int b) {int ans = 1;while(b) {if(b & 1) ans = (ans * a) % mod;a = (a * a) % mod,b >>= 1;}return ans % mod;}
int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> c;
	fac[0] = 1;
	for(int i = 1;i <= 200000;++i) fac[i] = (fac[i - 1] * i) % mod,invfac[i] = ksm(fac[i],mod - 2) % mod;
	for(int x = 1;x <= c;++x) {
		int U = ksm(ksm(x + 1,m) - 1,n) % mod,invU = 0,k = 1;
		for(int j = m;j >= 1;--j,k = k * (x + 1) % mod) {//这里
			if(j & 1) invU = (invU - C(m,j) * ksm(k - 1,n) + mod) % mod;
			else invU = (invU + C(m,j) * ksm(k - 1,n) + mod) % mod;
		}
		F[x] = (U + invU + mod) % mod;
		cerr << F[x] << "\n";
	}
	aU = F[c] % mod;
	int invaU = 0;
	for(int i = 1;i <= c;++i) invaU = (invaU + ksm(-1,i - 1) * C(c,i)  % mod* F[c - i] % mod) % mod;
	return cput << (aU - invaU + mod) % mod % mod << '\n',0;
}
/*
362 97 351
*/
2024/8/5 10:46
加载中...