whx's Blog

首先中文题面错了，是切比雪夫距离，而不是曼哈顿距离

切比雪夫距离的话，我们就强制每个维度上都必须要有一个取到0点，注意若干个面必须有一个取到0没有若干个面都没有取到0好做，那么直接容斥转化为后者即可。

#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();
}