这种题瞪不出势能函数时的暴力解决方法

可以考虑高斯消元。代码放在最后。

值得注意的是，势能函数的设计不是唯一的，因此高消会出现自由元，导致所有计算都废掉了。解决的办法是钦定一个元素的值，然后再消。比如这里我们钦定

f(0)=0

。然后如果不满足第二个条件（终态唯一且最小）就重新设定，这一部分的设定既然是小数据就可以直观感受势能值了。

注：一般来说钦定的值都要是开头的容易设置的值，比如

f(1)=1,f(0)=1

啥的。

CPP

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll mod=1e9+7;

ll qpow(ll x, ll y) {
  if (y < 0)
    y += mod - 1 + mod - 1;
  if (x == mod - 1)
    return y & 1 ? mod - 1 : 1;
  ll res = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      res *= x;
      res %= mod;
    }
    x *= x;
    x %= mod;
  }
  return res;
}

int n,tot;
ll a[505][505];
void gauss(int m){
  rep(i,1,n){
    int p=0;
    rep(j,i,m)if (a[j][i]){
      p=j;
      break;
    }
    if (!p)continue;
    else if (p!=i){
      rep(j,1,n+1)swap(a[i][j],a[p][j]);
    }
    rep(j,i+1,m)if (a[j][i]){
      ll iv=qpow(a[i][i],-1);
      drep(k,n+1,i){
        a[j][k]+=mod-a[j][i]*iv%mod*a[i][k]%mod;
        a[j][k]%=mod;
        // cout<<a[j][k]<<'\n';
      }
    }
  }
  drep(i,n,1){
    rep(j,i+1,n){
      (a[i][n+1]+=mod-a[j][n+1]*a[i][j]%mod)%=mod;
      a[i][j]=0;
    }
    (a[i][n+1]*=qpow(a[i][i],-1))%=mod;
    a[i][i]=1;
  }
}

int main() {
  scanf("%d",&n),++n;
  rep(x,0,n-2)rep(y,0,n-2){
    // 2(f(x)+f(y)-1)=(x+y)f(0)+f(x+1)+f(y+1)
    // => 2f(x)+2f(y)-(x+y)f(0)-f(x+1)-f(y+1)=2
    ++tot;
    a[tot][1]=mod-x-y;
    a[tot][x+1]+=2;
    a[tot][y+1]+=2;
    a[tot][x+2]+=mod-1;
    a[tot][y+2]+=mod-1;
    a[tot][n+1]+=2;
    a[tot][1]%=mod;
    a[tot][x+2]%=mod;
    a[tot][y+2]%=mod;
  }
  // Let f(0)=0
  a[++tot][1]=1;
  gauss(tot);
  rep(i,1,n)cout<<a[i][n+1]<<" \n"[i==n||i%3==0];
  
  return 0;
}

这种题瞪不出势能函数时的暴力解决方法

讨论操作

回复

相关推荐

这种题瞪不出势能函数时的暴力解决方法