結果

問題 No.890 移調の限られた旋法
ユーザー CinnamorollCinnamoroll
提出日時 2019-09-20 22:39:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 393 ms / 2,000 ms
コード長 7,345 bytes
コンパイル時間 1,991 ms
コンパイル使用メモリ 180,088 KB
実行使用メモリ 11,076 KB
最終ジャッジ日時 2024-09-14 18:39:37
合計ジャッジ時間 8,949 ms
ジャッジサーバーID
(参考情報)
judge6 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// warm heart, wagging tail,and a smile just for you!
//
// ▒█████▒▒
// ██████████▒
// ▒████████████▒
// ██████████████████
// ████████████████████▒
// ▒██████████████████████▒
// ▒███████████████████████
// ▒████▒▒▒▒▒▒█████████████████▒
// ███▒▒▒▒▒▒██████████████████████▒▒▒
// ▒██▒▒███████████████████████▒▒▒▒▒██████
// ▒█████████████████████████▒▒▒▒▒▒█████████▒
// ▒█████████████████████▒▒▒▒▒▒██████████████
// ▒████ ████▒▒▒▒▒████ ████▒
// ▒█████▒ ████ ▒▒▒▒███████ ████ ██████▒
// ▒██▒▒▒▒▒ ██████ █████████ ██████ ██▒▒▒██▒
// █████████ ████████ █████████ ████████ ▒▒▒▒█████
// ▒█████████ ██████ ████████▒ ██████ █████████
// ▒██████████ ████ █████▒▒▒▒▒▒ ████ ██████████
// ████████████ ▒▒▒▒▒▒▒████████ ███████████▒
// ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
// ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
// ▒▒▒▒▒▒▒▒▒██████████████ ███████▒▒▒▒███████████
// █████████████████████████ ███████▒▒▒██████████████▒
// █████████████████████████████ ███████▒▒▒██████████████████▒
// ██████████████████████████████████████████████████████████████████████
// ██████████████████████████████████████████████████████████████████▒
// ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << " = " << (x) << endl;
#define SP << " " <<
typedef pair<int,int> P;
#include <cstdint>
template <std::uint_fast64_t Modulus> class modint {
using u64 = std::uint_fast64_t;
u64 a;
public:
constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
constexpr u64 val() const noexcept { return a; }
constexpr modint operator+(const modint rhs) const noexcept {
return modint(*this) += rhs;
}
constexpr modint operator-(const modint rhs) const noexcept {
return modint(*this) -= rhs;
}
constexpr modint operator*(const modint rhs) const noexcept {
return modint(*this) *= rhs;
}
constexpr modint operator/(const modint rhs) const noexcept {
return modint(*this) /= rhs;
}
constexpr bool operator==(const modint rhs) const noexcept {
return modint(*this).val() == rhs.val();
}
modint &operator+=(const modint rhs) noexcept {
a += rhs.a;
if (a >= Modulus) {
a -= Modulus;
}
return *this;
}
modint &operator-=(const modint rhs) noexcept {
if (a < rhs.a) {
a += Modulus;
}
a -= rhs.a;
return *this;
}
modint &operator*=(const modint rhs) noexcept {
a = a * rhs.a % Modulus;
return *this;
}
modint &operator/=(modint rhs) noexcept {
u64 exp = Modulus - 2;
while (exp) {
if (exp % 2) {
*this *= rhs;
}
rhs *= rhs;
exp /= 2;
}
return *this;
}
};
using mint = modint<MOD>;
typedef vector<mint> vec;
typedef vector<vector<mint>> mat;
int m;
vec matmul(vec &dp, mat &mt){
vec ret(m,0);
REP(i,m) REP(j,m) ret[i] += mt[i][j]*dp[j];
return ret;
}
mat update(mat &mt){
mat ret(m,vec(m,0));
REP(i,m) REP(j,m) REP(k,m) ret[i][j] += mt[i][k]*mt[k][j];
return ret;
}
void matpow(vec &dp, mat &mt, int k){
m = dp.size();
while(k){
if(k%2) dp = matmul(dp,mt);
mt = update(mt);
k /= 2;
}
}
vector<int> divisor(const int n){
vector<int> ret;
for(int i=1;i*i<=n;i++){
if(n % i == 0){
ret.push_back(i);
if(i*i!= n) ret.push_back(n/i);
}
}
sort(ret.begin(),ret.end());
return ret;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,k;
cin >> n >> k;
int g = __gcd(n,k);
vector<int> list;
for(int i=2;i<=n;i+=2){
bool flag = true;
for(int j=3; j<=sqrt(i);j+=2){
if(i%j == 0){
flag = false;
break;
}
}
if(flag || i == 2){
int cnt = 0;
while(g%i==0) g /= i, cnt++;
if(cnt) g *= i,list.push_back(i);
}
if(i == 2) i--;
}
vector<int> a = divisor(g);
vec fact(n+1,1);
REP(i,n) fact[i+1] = fact[i]*(i+1);
mint ans = 0;
FOR(i,1,a.size()){
int cnt = 0;
REP(j,list.size()) if(a[i]%list[j]==0) cnt++;
if(cnt%2) ans += fact[n/a[i]]/fact[n/a[i]-k/a[i]]/fact[k/a[i]];
else ans -= fact[n/a[i]]/fact[n/a[i]-k/a[i]]/fact[k/a[i]];
}
cout << ans.val() << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0