QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#205797 | #6637. Perfect Strings | Geospiza# | WA | 34ms | 11680kb | C++14 | 1.0kb | 2023-10-07 17:26:44 | 2023-10-07 17:26:44 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
#define LL long long
#define Ma 1000005
#define mod 1000000007
#define N 1005
#define pb push_back
#define ls p<<1
#define rs p<<1|1
using namespace std;
ll mul[Ma],pre[Ma];
ll n,k;
ll po(ll p,ll x=mod-2)
{
ll sum=1;
while (x)
{
if (x&1) sum=1ll*sum*p%mod;
p=1ll*p*p%mod;
x>>=1;
}
return sum;
}
void pri()
{
mul[0]=1;
for (ll i=1;i<Ma;i++)
mul[i]=1ll*mul[i-1]*i%mod;
pre[Ma-1]=po(mul[Ma-1]);
for (ll i=Ma-2;i>=0;i--)
pre[i]=1ll*pre[i+1]*(i+1)%mod;
return;
}
ll C(ll x,ll y)
{
if (x<0||y<0||x>y) return 0;
return 1ll*mul[y]*pre[x]%mod*pre[y-x]%mod;
}
void sol()
{
cin>>n>>k;
if (k==1)
{
printf("1\n");
return;
}
ll ans=0,l=1,r=po(k-1,n),inv=po(k-1);
for (ll i=1;i<=n;i++)
{
l=1ll*l*k%mod;
r=1ll*r*inv%mod;
ans=(ans+1ll*l*r%mod*C(i-1,n-1)%mod)%mod;
}
printf("%d\n",ans);
}
int main()
{
pri();
ios::sync_with_stdio(0); cin.tie(0);
ll tt;
cin>>tt;
while (tt--)
sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 10ms
memory: 11616kb
input:
2 3 1 2 2
output:
1 6
result:
ok 2 number(s): "1 6"
Test #2:
score: -100
Wrong Answer
time: 34ms
memory: 11680kb
input:
100000 1 1 4 1 5 5 3 5 1 2 5 3 1 1 3 3 5 2 2 1 4 1 5 5 2 3 4 1 3 3 2 5 3 2 4 3 4 4 3 5 3 1 5 2 2 2 4 2 5 4 1 2 3 1 4 5 2 5 5 3 1 5 5 2 3 2 5 2 4 1 1 3 3 2 4 5 2 1 4 1 2 2 1 1 3 5 4 5 2 3 3 5 2 5 2 4 5 4 2 3 1 1 2 1 4 4 1 5 5 4 1 3 5 4 4 5 1 3 1 1 3 3 2 4 2 4 2 1 5 5 1 3 2 3 4 1 4 3 2 4 2 4 4 2 1 1 1...
output:
1 1 32805 405 2 1875 1 75 162 1 1 32805 15 1 75 45 18 375 1372 405 1 162 6 54 9604 2 1 3645 45 1875 5 162 18 162 1 3 18 3645 1 1 6 1 405 3645 15 405 45 28 9604 15 1 1 1372 5 9604 3 9604 3645 3 1 75 28 28 1 32805 3 15 1 375 28 28 54 1 1 32805 15 1372 3 1 2 15 75 1372 9604 32805 6 162 1372 162 15 5 2 ...
result:
wrong answer 3rd numbers differ - expected: '71445', found: '32805'