結果
問題 | No.906 Y字グラフ |
ユーザー |
![]() |
提出日時 | 2019-10-11 21:32:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,166 bytes |
コンパイル時間 | 3,159 ms |
コンパイル使用メモリ | 186,864 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 06:49:59 |
合計ジャッジ時間 | 3,842 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace std;typedef long long ll;typedef pair<int,int> P;typedef pair<int,P> P1;typedef pair<P,P> P2;#define pu push#define pb push_back#define mp make_pair#define eps 1e-7#define INF 1000000000#define mod 1000000007#define fi first#define sc second#define rep(i,x) for(int i=0;i<x;i++)#define repn(i,x) for(int i=1;i<=x;i++)#define SORT(x) sort(x.begin(),x.end())#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())ll x;ll modpow(ll x,ll n){ll res=1;while(n>0){if(n&1) res=res*x%mod;x=x*x%mod;n>>=1;}return res;}int main(){cin >> x;if(x <= 3) cout << 0 << endl;else{x --;ll all = 1, ans = 0;for(int i=1;i<=2;i++) all = all*((x-i)%mod)%mod;all = all*modpow(2ll,mod-2)%mod;if(x%3 == 0) {all --; ans++; }ll num = (x-1)/2;if(x%3 == 0) { num--; }all -= num*3LL%mod; ans += num;ans += all%mod*modpow(6LL,mod-2)%mod;cout << (ans%mod+mod)%mod << endl;}}