【每日一題】逆序?qū)?(思維)
逆序?qū)?/p>
https://ac.nowcoder.com/acm/problem/14731
Solution
取任意兩點,一者為0,一者為1,其他任意排列,則:
由于取模,所以有兩種選擇:
1.逆元
2.預(yù)處理
由于組合數(shù)比較小,所以選擇了預(yù)處理。
Code
#include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ll long long #define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; inline ll read(){ll s=0,w=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;} void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); } ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;}a = (a*a)%p;b >>= 1;}return ans%p;} const int mo=998244353; const int mod=1000000007; const int manx=1e5+5; int main(){ ll n=read(); if(n==1) cout<<0; else{ ll a=n,b=n-1; if(a&1) b/=2; else a/=2; a%=mod,b%=mod; cout<<a*b%mod*qp(2,n-2,mod)%mod<<endl; } return 0; }