NC15690. 敬老师的手环Ⅱ
描述
敬老师是一位很喜欢手环的老师。话说敬老师即将去和barriery一起到北京实tong习ju，并且再过几天就是5.20，敬老师突发奇想，想要再DIY一个手环然后送给barriery。现在敬老师拥有的材料是一堆1*2的小矩形，每个小矩形都是一样的，他想要用这些小矩形拼出一个宽度为3周长为n的手环（手环靠近手的一侧和远离手的一侧是不同的）。于是他想要知道自己能拼出多少种不同的手环。
但是敬老师最近正在为实习做准备，没时间算这个，于是就把问题丢给了无所事事的wy。然而wy自己又只能看队友去实gao习ji，又要求这个题，于是就很郁闷，所以他把问题扔给了你。现在，你能帮wy解决这个问题吗？
输入描述
多组数据，数据组数不超过1000，请处理到文件结束。每组数据占一行，包含一个数（n <= 1e9）。
输出描述
每组数据输出一个数，即不相同的手环的种类数，要求答案对1e9+7取模。
示例1
输入:
1 2 3 4
输出:
0 6 0 11
C++14(g++5.4) 解法, 执行用时: 450ms, 内存消耗: 868K, 提交时间: 2018-06-05 17:33:48
#include <bits/stdc++.h>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
#define REP(X,N) for(int X=0;X<N;X++)
typedef vector<vector<int> > Mat;
#define MOD 1000000007
Mat M = Mat(6, vector<int>(6, 0));
Mat I = Mat(6, vector<int>(6, 0));
Mat mul(Mat& a, Mat& b) {
auto c = Mat(6, vector<int>(6, 0));
REP(i,6)
REP(j,6)
REP(k,6) {
c[i][j] += 1LL * a[i][k] * b[k][j] % MOD;
if(c[i][j] >= MOD) c[i][j] -= MOD;
}
return c;
}
hash_map<int, Mat> mp;
Mat pm(int n) {
if(n == 0) return I;
if(n == 1) return M;
if(mp.count(n)) return mp[n];
auto b = pm(n / 2);
b = mul(b, b);
if(n & 1) b = mul(b, M);
return b;
}
int pow_mod(int a, int n) {
int r = 1;
while(n) {
if(n%2)
r=1LL*r*a%MOD;
a=1LL*a*a%MOD;
n>>=1;
}
return r;
}
#define MAXN 100000
int vis[MAXN]={1,1};
int prime[MAXN], n_prime;
void Eular() {
n_prime=0;
for(int i = 2; i < MAXN; i++) {
if(!vis[i]) {
prime[n_prime++] = i;
}
for(int j = 0; j < n_prime && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
vector<pair<int, int> > dispose(int n) {
vector<pair<int, int> > vec;
for(int i = 0; prime[i] * prime[i] <= n; i++) {
int c = 0;
while(n % prime[i] == 0) {
n /= prime[i];
c++;
}
if(c) vec.push_back(make_pair(prime[i], c));
}
if(n > 1) vec.push_back(make_pair(n, 1));
return vec;
}
int phi(int n, vector<pair<int,int> >& ps) {
int ans = n;
for(auto p : ps) {
if(n % p.first == 0) {
ans = ans / p.first * (p.first-1);
}
}
return ans;
}
int gao(int n) {
auto res = pm(n-1);
long long ans = res[1][0] * 4LL + res[5][0] * 2LL + res[4][1] * 4LL + (n % 2 == 0 ? 2 : 0);
//cout<<n<<' '<<ans<<endl;
return ans % MOD;
}
int main() {
ios::sync_with_stdio(false);
Eular();
M[0][1] = 1; M[1][0] = 1;
M[0][3] = 1; M[3][0] = 1;
M[0][5] = 1; M[5][0] = 1;
M[1][4] = 1; M[4][1] = 1;
M[2][3] = 1; M[3][2] = 1;
REP(i,6) I[i][i] = 1;
int n;
while(cin>>n){
if(n % 2 == 1) {
cout<<0<<endl;
continue;
}
auto ps = dispose(n);
int ans = 0;
int total = 1;
for(auto p : ps)
total *= p.second + 1;
for(int i = 0; i < total; i++) {
int i_ = i;
int x = 1;
for(auto p : ps) {
for(int j = 0; j < i_ % (p.second + 1); j++)
x *= p.first;
i_ /= p.second + 1;
}
ans += 1LL * gao(x) * phi(n / x, ps) % MOD;
ans %= MOD;
}
ans = 1LL * ans * pow_mod(n, MOD-2) % MOD;
cout<<ans<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 494ms, 内存消耗: 488K, 提交时间: 2018-04-27 18:29:04
#include <bits/stdc++.h>
using namespace std;
#define REP(X,N) for(int X=0;X<N;X++)
typedef vector<vector<int> > Mat;
#define MOD 1000000007
Mat mul(Mat& a, Mat& b) {
auto c = Mat(6, vector<int>(6, 0));
REP(i,6)
REP(j,6)
REP(k,6) {
c[i][j] += 1LL * a[i][k] * b[k][j] % MOD;
c[i][j] %= MOD;
}
return c;
}
Mat pm(Mat a, int n) {
auto r = Mat(6, vector<int>(6, 0));
REP(i,6) r[i][i] = 1;
while(n) {
if(n%2)
r=mul(r,a);
a=mul(a,a);
n>>=1;
}
return r;
}
int pow_mod(int a, int n) {
int r = 1;
while(n) {
if(n%2)
r=1LL*r*a%MOD;
a=1LL*a*a%MOD;
n>>=1;
}
return r;
}
vector<pair<int, int> > dispose(int n) {
vector<pair<int, int> > vec;
for(int i = 2; i * i <= n; i++) {
int c = 0;
while(n % i == 0) {
n /= i;
c++;
}
if(c) vec.push_back(make_pair(i, c));
}
if(n > 1) vec.push_back(make_pair(n, 1));
return vec;
}
int phi(int n, vector<pair<int,int> >& ps) {
int ans = n;
for(auto p : ps) {
if(n % p.first == 0) {
ans = ans / p.first * (p.first-1);
}
}
return ans;
}
Mat M = Mat(6, vector<int>(6, 0));
int gao(int n) {
auto res = pm(M, n-1);
long long ans = res[1][0] * 4LL + res[5][0] * 2LL + res[4][1] * 4LL + (n % 2 == 0 ? 2 : 0);
//cout<<n<<' '<<ans<<endl;
return ans % MOD;
}
int main() {
ios::sync_with_stdio(false);
M[0][1] = 1; M[1][0] = 1;
M[0][3] = 1; M[3][0] = 1;
M[0][5] = 1; M[5][0] = 1;
M[1][4] = 1; M[4][1] = 1;
M[2][3] = 1; M[3][2] = 1;
int n;
while(cin>>n){
if(n % 2 == 1) {
cout<<0<<endl;
continue;
}
auto ps = dispose(n);
int ans = 0;
for(int i = 1; i * i <= n; i++) {
if(n % i == 0) {
ans += 1LL * gao(i) * phi(n / i, ps) % MOD;
ans %= MOD;
if(n / i != i)
ans += 1LL * gao(n / i) * phi(i, ps) % MOD;
ans %= MOD;
}
}
ans = 1LL * ans * pow_mod(n, MOD-2) % MOD;
cout<<ans<<endl;
}
return 0;
}