QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#418917 | #8339. Rooted Tree | youthpaul | TL | 322ms | 3740kb | C++20 | 3.6kb | 2024-05-23 16:26:37 | 2024-05-23 16:26:37 |
Judging History
answer
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3f;
const long long INFLL=1e18;
// typedef long long ll;
using ll = int;
template<class T>
constexpr T power(T a, ll b){
T res = 1;
while(b){
if(b&1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
constexpr ll mul(ll a,ll b,ll mod){ //快速乘,避免两个long long相乘取模溢出
ll res = a * b - ll(1.L * a * b / mod) * mod;
res %= mod;
if(res < 0) res += mod; //误差
return res;
}
template<ll P>
struct MLL{
ll x;
constexpr MLL() = default;
constexpr MLL(ll x) : x(norm(x % getMod())) {}
static ll Mod;
constexpr static ll getMod(){
if(P > 0) return P;
return Mod;
}
constexpr static void setMod(int _Mod){
Mod = _Mod;
}
constexpr ll norm(ll x) const{
if(x < 0){
x += getMod();
}
if(x >= getMod()){
x -= getMod();
}
return x;
}
constexpr ll val() const{
return x;
}
explicit constexpr operator ll() const{
return x; //将结构体显示转换为ll类型: ll res = static_cast<ll>(OBJ)
}
constexpr MLL operator -() const{ //负号,等价于加上Mod
MLL res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLL inv() const{
assert(x != 0);
return power(*this, getMod() - 2); //用费马小定理求逆
}
constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象
x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用
return *this;
}
constexpr MLL& operator += (MLL rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLL& operator -= (MLL rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLL& operator /= (MLL rhs) & {
return *this *= rhs.inv();
}
friend constexpr MLL operator * (MLL lhs, MLL rhs){
MLL res = lhs;
res *= rhs;
return res;
}
friend constexpr MLL operator + (MLL lhs, MLL rhs){
MLL res = lhs;
res += rhs;
return res;
}
friend constexpr MLL operator - (MLL lhs, MLL rhs){
MLL res = lhs;
res -= rhs;
return res;
}
friend constexpr MLL operator / (MLL lhs, MLL rhs){
MLL res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream& operator >> (std::istream& is, MLL& a){
ll v;
is >> v;
a = MLL(v);
return is;
}
friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){
return os << a.val();
}
friend constexpr bool operator == (MLL lhs, MLL rhs){
return lhs.val() == rhs.val();
}
friend constexpr bool operator != (MLL lhs, MLL rhs){
return lhs.val() != rhs.val();
}
};
const ll mod = 1e9 + 9;
using Z = MLL<mod>;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int m, k;
std::cin >> m >> k;
Z ans = 0;
Z A = 0;
fore(i, 0, k){
Z inv = 1 / Z((m - 1) * i + 1);
ans += A * inv + 1;
A = A * ((m - 1) * (i + 1) + 1) * inv + m;
}
ans *= m;
std::cout << ans << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 322ms
memory: 3740kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: -100
Time Limit Exceeded
input:
48 6713156