AOJ 2378: SolveMe
問題
となるようなA, Bの組の個数を1,000,000,007で割ったものを求める. (A, Bの条件については問題文参照)
解法
まず
にを代入し整理すると、となる.
を求めれば良い.
ただし、 は N次元ベクトルで、 で、置換の大きさは同じであるとする. 置換の大きさは、
と表される. これは、
である.
標準基底のスカラー倍について計算してから、DPで計算すればよい.
実際に計算する場合は、をで割ったものを計算するほうが簡単である.
コーナーケースがあるので注意する.
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; #define N 1024 ll inv[N], fact[N], ifact[N], D[N][N], iD[N][N], dp[N][N], dp2[2][N][N]; ll mod = 1000000007; ll n, x, y, z, t[2]; void update(ll a, ll t, ll d[][N]){ d[a][0] = 1; int v = __gcd(a, t); int b = a/v; for(int i = n/b; i >= 1; i--) for(int j = 1; j <= i/v; j++) (d[b][i]+=d[b][i-j*v]*D[a][j])%=mod; } int main(){ scanf("%ld%ld%ld%ld",&n,&x,&y,&z); t[0] = abs(x-y+z); t[1] = 2; inv[1] = 1; for(int i = 2; i <= n; i++) inv[i] = inv[mod%i]*(mod-mod/i)%mod; fact[0] = ifact[0] = 1; for(int i = 1; i <= n; i++){ fact[i] = fact[i-1]*i%mod; ifact[i] = ifact[i-1]*inv[i]%mod; } for(int i = 1; i <= n; i++){ D[i][0] = iD[i][0] = 1; for(int j = 1; j <= n/i; j++){ D[i][j] = D[i][j-1]*inv[i*j]%mod; iD[i][j] = iD[i][j-1]*i*j%mod; } } if(!x&&!y&&!z){ for(int i = 1; i <= 2; i++) update(i, t[0], dp2[0]); ll res = dp2[0][1][n]*fact[n]%mod; for(int i = 0; i < n; i++) (res*=n)%=mod; printf("%ld\n", res); return 0; } for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) update(i, t[j], dp2[j]); dp[0][0] = 1; for(int i = 1; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= j/i; k++) (dp[i][j]+=dp[i-1][j-i*k]*dp2[0][i][k]%mod*dp2[1][i][k]%mod*iD[i][k])%=mod; printf("%ld\n",dp[n][n]*fact[n]%mod); return 0; }