Skip to content

Instantly share code, notes, and snippets.

Created March 7, 2016 17:48
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anonymous/3817f7de6696dc354763 to your computer and use it in GitHub Desktop.
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
#include <map>
#include <iomanip>
#include <stack>
#include <sstream>
#include <queue>
#include <set>
#include <functional>
#define endl '\n'
#define eps 1e-9
#define ll long long int
using namespace std;
const ll MOD = 1000000007;
typedef vector<vector<ll> > matrix;
matrix mul(matrix A, matrix B, int k){
matrix C(k, vector<ll>(k));
for (int i = 0; i < k; i++) for(int j = 0; j < k; j++) for (int x = 0; x < k; x++){
C[i][j] = (C[i][j] + A[i][x]*B[x][j])%MOD;
}
return C;
}
matrix pow(matrix A, int p, int k){
if (p == 1) return A;
if (p%2)
return mul(A, pow(A, p-1, k), k);
matrix X = pow(A, p/2, k);
return mul(X, X, k);
}
class DivFree{
public:
int dfcount(int n, int k){
if (n == 1) return k;
matrix T(k, vector<ll>(k, 0));
for (int i = 1; i <= k; i++){
for (int j = 1; j <= k; j++){
if (j <= i || j%i != 0){
T[i-1][j-1] = 1;
}
}
}
T = pow(T, n-1, k);
ll ret = 0;
for (int i = 0; i < k; i++){
for (int j = 0; j < k; j++){
ret += T[i][j];
}
ret%= MOD;
}
ret %= MOD;
int ans = (int)ret;
return ans;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment