首先中文题面错了，是切比雪夫距离，而不是曼哈顿距离
切比雪夫距离的话，我们就强制每个维度上都必须要有一个取到0点，注意若干个面必须有一个取到0没有若干个面都没有取到0好做，那么直接容斥转化为后者即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <iostream>#include <cstdio>#include <algorithm>#define dep(i,a,b) for(int i = a; i >= b; i--)#define rep(i,a,b) for(int i = a; i <= b; i++)using namespace std;const int M = 1000000007;int pow(int a, int b, int c){ int w = 1; for(;b;b >>= 1, a = 1LL * a * a % c) if (b & 1) w = 1LL * w * a % c; return w;}const int N = 1010;int fac[N], inv[N];int c(int n, int m){ return 1LL * fac[n] * inv[m] % M * inv[n - m] % M;}int n;int calc(int d){ if (d == 0) return 1; int ans = 0, t = 1; rep(i,0,n){ int tmp = 1LL * c(n,i) * pow(2, 1LL * pow(d, i, M - 1) * pow(d + 1, n - i, M - 1) % (M - 1), M) % M; ans += t * tmp, ans %= M; t = -t; } return ans;}void work(){ int d; scanf("%d%d",&n,&d); int ans = (calc(d) - calc(d - 1)) % M; if (ans < 0) ans += M; printf("%d\n",ans);}int main(){ fac[0] = 1; rep(i,1,1000) fac[i] = 1LL * fac[i - 1] * i % M; inv[1000] = pow(fac[1000], M - 2, M); dep(i,1000,1) inv[i - 1] = 1LL * inv[i] * i % M; int T; scanf("%d",&T); while (T--) work();} |
评论 (0)
