NC17669. The number of circuits
描述
输入描述
The first and only line contains two integers, which are k and n.1 <= k <= 72k+1 <= n <= 109
输出描述
The first and only line contains the answer.
示例1
输入:
2 5
输出:
11
说明:
The answer is not 22.示例2
输入:
3 8
输出:
278528
说明:
Try a brute force search...C++14(g++5.4) 解法, 执行用时: 373ms, 内存消耗: 16480K, 提交时间: 2019-02-18 23:45:12
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
namespace linear_seq {
const int N=10010;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if (_c[i])
rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
// printf("SIZE %d\n",SZ(b));
ll ans=0,pnt=0;
int k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
Md.clear();
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0;
res[0]=1;
while ((1ll<<pnt)<=n) pnt++;
for (int p=pnt;p>=0;p--) {
mul(res,res,k);
if ((n>>p)&1) {
for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if (ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,SZ(s)) {
ll d=0;
rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if (d==0) ++m;
else if (2*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else {
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};
int a[2020][2020];
ll det(int n) {
ll ans = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
while (a[j][i] != 0) {
int u = a[i][i] / a[j][i];
for (int k = 0; k < n; k++) {
int t = (a[i][k] - (ll)a[j][k] * u % mod + mod) % mod;
a[i][k] = a[j][k];
a[j][k] = t;
}
ans = -ans;
}
}
ans = ans * a[i][i] % mod;
}
if (ans < 0) {
ans += mod;
}
return ans;
}
ll work(int k, int n) { //构造矩阵 计算点数为n的欧拉回路个数
memset(a, 0, sizeof a);
for (int i = 0; i < n; i++) {
a[i][i] = k;
for (int j = 1; j <= k; j++) {
a[i][(i + j) % n] = -1;
}
}
ll t = 1;
for (int i = 1; i < k; i++) { //度数-1的阶乘
t = t * i % mod;
}
return (ll)det(n - 1) * powmod(t, n) % mod; // 每个点的度数都一样 所以直接快速幂。
}
int main() {
int k;
ll n;
cin >> k >> n;
vector<int> a;
for (int i = 2 * k + 1; i <= (1 << k)+ 2 * k + 1; i++) { //为什么是1<<k这么多项 也也不知道 题解说的。。。 正常写就在不超时的情况下尽量写大点呗
a.push_back(work(k, i));
}
cout << linear_seq::gao(a, n - (2 * k + 1)) << endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 121ms, 内存消耗: 736K, 提交时间: 2018-08-20 18:53:19
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)
#define sz(a) (int)a.size()
#define de(a) cout << #a << " = " << a << endl
#define dd(a) cout << #a << " = " << a << " "
#define all(a) a.begin(), a.end()
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//---
const int N = 222, P = 1e9+7;
int add(int a, int b) {
if((a += b) >= P) a -= P;
return a;
}
int sub(int a, int b) {
if((a -= b) < 0) a += P;
return a;
}
int mul(int a, int b) {
return 1ll * a * b % P;
}
int kpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(r, a);
a = mul(a, a);
b >>= 1;
}
return r;
}
vi BM(vi s) {
vi C(1, 1), B(1, 1);
int L = 0, m = 1, b = 1;
rep(n, 0, sz(s)) {
ll d = 0;
rep(i, 0, L+1) (d += 1ll * C[i] * s[n-i]) %= P;
if(d == 0) ++m;
else {
vi T = C;
ll c = P - d * kpow(b, P - 2) % P;
while(sz(C) < sz(B) + m) C.pb(0);
rep(i, 0, sz(B)) C[i + m] = add(C[i + m], mul(c, B[i]));
if(2 * L <= n) {
L = n + 1 - L, B = T, b = d, m = 1;
} else {
++m;
}
}
}
reverse(all(C));
rep(i, 0, sz(C)) C[i] = P - C[i];
return vi(C.begin(), C.end() - 1);
}
int linear_recurrence(ll n, int m, vi a, vi c) {
vector<ll> v(m, 0), u(m<<1, 0);
v[0] = 1;
for(ll x = 0, W = n ? 1ll<<(63 - __builtin_clzll(n)) : 0; W; W >>= 1, x <<= 1) {
fill(all(u), 0);
int b = !!(n & W); if(b) x++;
if(x < m) u[x] = 1;
else {
rep(i, 0, m) rep(j, 0, m) (u[i + b + j] += v[i] * v[j]) %= P;
per(i, m, 2*m) rep(j, 0, m) (u[i - m + j] += c[j] * u[i]) %= P;
}
copy(u.begin(), u.begin() + m, v.begin());
}
ll ans = 0;
rep(i, 0, m) (ans += v[i] * a[i]) %= P;
return ans;
}
namespace S {
int n;
int a[N][N];
int det() {
int ans = 1;
rep(i, 1, n) {
rep(j, i+1, n) while(a[j][i]) {
int t = a[i][i] / a[j][i];
rep(k, i, n) a[i][k] = sub(a[i][k], mul(a[j][k], t));
rep(k, i, n) swap(a[i][k], a[j][k]);
ans = P - ans;
}
if(a[i][i] == 0) return 0;
ans = mul(ans, a[i][i]);
}
return ans;
}
int solve(int k, int n) {
memset(a, 0, sizeof(a));
rep(i, 0, n) {
a[i][i] = k;
rep(j, 1, k+1) a[i][(i+j)%n] = P-1;
}
S::n = n;
return det();
}
}
int len;
vi s;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int k, n;
cin >> k >> n;
rep(i, 2*k+1, N) s.pb(S::solve(k, i));
vi T = BM(s);
int ans = linear_recurrence(n - 2 * k - 1, sz(T), s, T);
int res = 1;
rep(i, 1, k) res = mul(res, i);
ans = mul(ans, kpow(res, n));
cout << ans << endl;
return 0;
}