本文共 1049 字，大约阅读时间需要 3 分钟。

从序号最大的点开始考虑

考虑$(i,j)$(其中$i<j$)这条边,选和不选的方案数放在$i$点考虑

这样可以做到不重不漏

设$p$表示权值大于$i$且被选择的点数,$q$表示权值大于$i$且没被选择的点数

①.若点$i$被选择(只考虑$(i,j)$边,其中$i<j$)

那么至少存在一个代价更大且没被选择的点和$i$相连

如果不是这样,完全可以不选$i$而把其他小于$i$的点全选上,更优

如果是这样,那么可以保证$i$会被选择

方案数是$(2^q-1)\ast 2^p$

②.若点$i$没有被选择(只考虑$(i,j)$边,其中$i<j$)

显然$i$不可能和其他代价更大且没有被选择的点相连

显然$i$可能和所有代价更大且被选择的点相连

这样最优,方案数是$2^q$

累乘即是答案

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;const int mod = 1e9+7;int base[maxn],n;char a[maxn];signed main(){
   	base[0] = 1;	for(int i=1;i<=1000000;i++)	base[i] = base[i-1]*2%mod; 	while( cin >> n >> ( a+1 ) )	{
   		int p = 0  , q = 0 , ans = 1;//被选择的点,没有被选择的点 		reverse( a+1,a+1+strlen(a+1) );		for(int i=strlen(a+1)+1;i<=n;i++)	a[i] = '0';		for(int i=n;i>=1;i--)		{
   			if( a[i]=='0' )//不被选择				ans = ans*base[p]%mod,q++;			else 				ans = ans*( base[q]-1 )%mod*base[p]%mod,p++;		}		cout << (ans%mod+mod)%mod << endl;	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116542170 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！