题意:
求所有长度为n的01串中满足如下条件的二元组个数:
设第i位和第j位分别位ai和aj(i<j),则ai=1,aj=0。
答案对1e9+7取模。
题解:
只有当两个位置i,j a[i]=1,a[j]=0时会对答案构成1的贡献,所以
其中第二项为i,j的方案数,第一项为固定i,j后其他位置的方案数
代码:
#pragma GCC optimize(2) #include<bits/stdc++.h> #define ls rt<<1 #define rs rt<<1|1 #define pb push_back #define fi first #define se second #define yes puts("YES") #define no puts("NO") #define ios ios::sync_with_stdio(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef vector<int> VI; const int maxn = 1e6 + 6; const LL inf = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;} LL inv(LL x){return qp(x,mod-2);} int _,n,a[maxn]; int main(){ LL n;scanf("%lld",&n); if(n==1) {printf("0\n");return 0;} LL a = qp(2,n-2);n%=mod; printf("%lld",n*(n-1)%mod*a%mod*inv(2)%mod); }