tyvj1996 工作分配2

沦落到写tyvj的题解了。不过看在这题之前只有7人过的份上就写一下好了。

式子是容斥，比较好想。answer = sigma((-1)^i * m^(n-i) * C(m, i)) (0 <= i <= m)

m^(n-i)这一块用快速幂就好了。

然后对于前一题因为m很小所以用m^2把组合数弄出来就行了。但是这里m^2就T到明天去了。

观察

C(m, i) = m!/(i! * (m-i)!) 

=> C(m, i - 1) = m! / ((i-1)! * (m-i+1)!) 

=> C(m, i) = C(m, i - 1) / i * (m - i + 1)

这样递推用逆元来做就是O(m * lgm)的时间了。

然后这题就这样了。代码很短。

#include <iostream>

#include <memory.h>

using namespace std;

#define _l (long long int)

typedef long long qw;

const int maxm = 1000009;

const int mod = 1e9 + 7;

int cm[maxm];

int modPow(int a, qw x) {

int s = 1;

for (; x; x >>= 1, a = _l a * a % mod)

if (x & 1)

s = _l s * a % mod;

return s;

}

void preComb(int m) {

memset(cm, 0, sizeof(cm));

cm[0] = 1;

for (int i = 1; i <= m; ++ i)

cm[i] = _l cm[i - 1] * modPow(i, mod - 2) % mod * (m - i + 1) % mod;

}

int main() {

int m, s = 0;

qw n;

cin >> n >> m;

n %= mod - 1;

preComb(m);

for (int i = 0, k = 1; i <= m; ++ i, k = -k)

s = (_l s + _l k * cm[i] * modPow(m - i, n) % mod + mod) % mod;

cout << s << endl;

}