solution
首先单独考虑蓝色和红色的染色方式。
如果只染蓝色(红色)和绿色,我们枚举一个蓝色边的数量x,然后方案数就是。所以总的方案数就是。
然后容斥合并蓝色和红色的方案。枚举蓝色和红色边重复的数量x,那么答案就是。所以最终答案就是
注意到上面求单个的过程是的。预处理f数组的复杂度就是。所以考虑用更优秀的方法求f。
将f打表如下:
找规律或OEIS发现递推式:。然后就可以线性预处理了。
总复杂度
code
/* * @Author: wxyww * @Date: 2020-04-09 15:26:44 * @Last Modified time: 2020-04-09 19:30:33 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 10000004,mod = 1e9 + 7; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int jc[N],inv[N],f[N]; ll qm(ll x,ll y) { ll ret = 1; for(;y;y >>= 1,x = x * x % mod) if(y & 1) ret = ret * x % mod; return ret; } ll C(int n,int m) { return 1ll * jc[n] * inv[m] % mod * inv[n - m] % mod; } ll A(int n,int m) { return 1ll * jc[n] * inv[n - m] % mod; } void solve(int n) { ll ans = 0; for(int i = 0;i <= n;++i) ans += C(n,i) * A(n,i); cout<<ans<<endl; } int main() { int n = read(); jc[0] = 1; for(int i = 1;i <= n;++i) jc[i] = 1ll * jc[i - 1] * i % mod; inv[n] = qm(jc[n],mod - 2); for(int i = n - 1;i >= 0;--i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod; // for(int i = 1;i <= n;++i) { // solve(i); // } // return 0; f[0] = 1;f[1] = 2; for(int i = 2;i <= n;++i) f[i] = (2ll * i * f[i - 1] - 1ll * f[i - 2] * (i - 1) % mod * (i - 1) % mod) % mod; // cout<<A(n,0)<<endl; ll ans = 0; for(int i = 0;i <= n;++i) { ll k = 1; if(i & 1) k = -1; ans += k * C(n,i) * A(n,i) % mod * f[n - i] % mod * f[n - i] % mod; ans %= mod; } printf("%lld\n",(ans + mod) % mod); return 0; }