QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#118446 | #6137. Sub-cycle Graph | chenxinyang2006 | WA | 94ms | 4752kb | C++14 | 4.0kb | 2023-07-03 16:02:31 | 2023-07-03 16:02:34 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
template <int P>
class mod_int
{
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const
{
Z res = 1, t = *this;
while (k)
{
if (k & 1)
res *= t;
if (k >>= 1)
t *= t;
}
return res;
}
Z &operator++()
{
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--()
{
x ? --x : x = P - 1;
return *this;
}
Z operator++(int)
{
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int)
{
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs)
{
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs)
{
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z operator-()
{
return -x;
}
Z &operator*=(const Z &rhs)
{
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) \
{ \
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
friend istream& operator>>(istream& is, mod_int& x)
{
long long tmp;
is >> tmp;
x = tmp;
return is;
}
friend ostream& operator<<(ostream& os, const mod_int& x)
{
os << x.val();
return os;
}
};
using Z = mod_int<mod>;
Z power(Z p,ll k){
Z ans = 1;
while(k){
if(k % 2 == 1) ans *= p;
p *= p;
k /= 2;
}
return ans;
}
Z fact[100005],ifac[100005],P[100005];
Z C(int N,int M){
if(N < M || M < 0) return 0;
return fact[N] * ifac[M] * ifac[N - M];
}
void init(int L){
fact[0] = 1;
rep(i,1,L) fact[i] = fact[i - 1] * i;
ifac[L] = 1 / fact[L];
per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
P[0] = 1;
rep(i,1,L) P[i] = P[i - 1] / 2;
}
int T,n,m;
void solve(){
ll tmp;
scanf("%d%lld",&n,&tmp);
if(tmp > n){
printf("0\n");
return;
}
if(tmp == n){
printf("%d\n",fact[n - 1].val());
return;
}
m = n - tmp;
Z ans = 0;
rep(k,0,m) ans += C(m,k) * P[m - k] * C(n - m - 1,m - k - 1);
ans *= fact[n] * ifac[m];
printf("%d\n",ans.val());
}
int main(){
scanf("%d",&T);
init(100000);
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 13ms
memory: 4752kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: -100
Wrong Answer
time: 94ms
memory: 4736kb
input:
17446 3 0 3 1 3 2 3 3 4 0 4 1 4 2 4 3 4 4 5 0 5 1 5 2 5 3 5 4 5 5 6 0 6 1 6 2 6 3 6 4 6 5 6 6 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 8 0 8 1 8 2 8 3 8 4 8 5 8 6 8 7 8 8 9 0 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 10 0 10 1 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11...
output:
0 3 3 2 0 6 15 12 6 0 10 45 90 60 24 0 15 105 375 630 360 120 0 21 210 1155 3465 5040 2520 720 0 28 378 2940 13545 35280 45360 20160 5040 0 36 630 6552 42525 170100 393120 453600 181440 40320 0 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 362880 0 55 1485 24750 273735 2047815 10239075 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'