QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#21344#2817. 鸽鸽的分割DoorKickers#AC ✓3ms3608kbC++20833b2022-03-04 16:19:052022-05-08 02:54:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:54:34]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3608kb
  • [2022-03-04 16:19:05]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 1e6 + 5;

ll qpow(ll x,ll y){
    ll ans=1;
    x%=mod;
    while(y>0){
        if(y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}

ll C(ll x,ll y){
    ll ans=1;
    for(ll i=x;i>x-y;i--){
        ans=ans*i%mod;
    }
    ll res=1;
    for(ll i=1;i<=y;i++){
        res=res*i%mod;
    }
    return ans*qpow(res,mod-2)%mod;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    while (cin>>n)
    cout<<((C(n,2)+C(n,4)+1)%mod+mod)%mod<<'\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 3608kb

input:

0
1
2
3
4
5
6
7
8
9
10
20
30
40
50
60
61
62
63
64

output:

1
1
2
4
8
16
31
57
99
163
256
5036
27841
92171
231526
489406
523686
559737
597619
637393

result:

ok 20 lines