旧网站如何优化,tomcat部署wordpress,生鲜电商网站建设,青岛专业网站制作题干#xff1a;
蒜头国有 nn 座城市#xff0c;编号分别为 0,1,2,3,\ldots,n-10,1,2,3,…,n−1。编号为 xx 和 yy 的两座城市之间如果要修高速公路#xff0c;必须花费 x|yx∣y 个金币#xff0c;其中|表示二进制按位或。
吝啬的国王想要花最少的价格修建高速公路#…题干
蒜头国有 nn 座城市编号分别为 0,1,2,3,\ldots,n-10,1,2,3,…,n−1。编号为 xx 和 yy 的两座城市之间如果要修高速公路必须花费 x|yx∣y 个金币其中|表示二进制按位或。
吝啬的国王想要花最少的价格修建高速公路使得所有城市可以通过若干条高速公路互相达到。现在请你求出 n2019n2019 时一共有多少不同的方案能让所有城市连通并且造价最低。方案数可能很大你只需输出对 10^971097 取模的结果。
样例输入复制
无
样例输出复制
无
解题报告 这题首先看最终答案是多少显然不难发现因为每个结点都至少连一条边所以结果不可能低于0123..n-1。又因为可以每条边都和0连所以可以做到0123..n-1。接下来就是构造答案的方案数了。
这个最终答案的构造也可以直接n^2建图然后跑MST就完事了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
int main()
{int n 2019;ll ans 1;for (int i 1; i n; i) {ll tmp 0;for(int j 0; ji; j) {if((i|j) i) {tmp;}}ans (ans * tmp)%mod;}printf(%lld\n, ans);return 0 ;}
还有一种nlogn的做法
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e97;
int main()
{int n 2019;ll ans 1;for (int i 1; i n; i) {int t 0;//代表i这个数有几个1.for (int j 0; i j 0; j) {if (i j 1) t;}ans ans * ((1 t) - 1) % mod;}printf(%lld\n, ans);return 0 ;}
