Codeforces Round #177 (Div. 2) 题解 - c++编程基础

,flag); return 0; } inline void check() { int ok=1;memset(f,0,sizeof(f)); for (int i=2;i<=k&&ok;i++) ok&=work(i,i); if (ok) num++; } void dfs(int now) { if (now==k+1) {check();return;} for (int i=1;i<=k;i++) a[now]=i,dfs(now+1); } int main() { scanf("%I64d%I64d",&n,&k);ans=k; for (i=1;i<=n-k;i++) (ans*=(n-k))%=P; dfs(2); if (num) (ans*=num)%=P; printf("%I64d",ans); return 0; }

【E】

E. Polo the Penguin and XOR operation time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.

For permutation p?=?p0,?p1,?...,?pn, Polo has defined its beauty ― number $\$ .<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkV4cHJlc3Npb24gPGltZyBhbGlnbj0="middle" class="tex-formula" src="https://www.cppentry.com/upload_files/article/49/1_hb834__.png" alt="\"> means applying the operation of bitwise excluding "OR" to numbers x and y. This operation exists in all modern programming languages, for example, in language C++ and Java it is represented as "^" and in Pascal ― as "xor".

Help him find among all permutations of integers from 0 to n the permutation with the maximum beauty.

Input

The single line contains a positive integer n (1?≤?n?≤?106).

Output

In the first line print integer m the maximum possible beauty. In the second line print any permutation of integers from 0 to n with the beauty equal to m.

If there are several suitable permutations, you are allowed to print any of them.

Sample test(s) input

output

20
0 2 1 4 3

题意很清楚，求0~N的排列Ai，使得max{Σi^A[i]}。

开始以为是从大到小枚举i，在字母树中贪心地找与它尽量能匹配的。后来打表后发现是一一对应的，不用这么麻烦。如果i没有被匹配过，我们可以构造出k

这里是打表程序：

#include
      
       
#include
       
         #include
        
          using namespace std; int n,sum,t,now,ans,i,wri[10005][105],a[105]; int main() { freopen("1.txt","w",stdout); for (n=3;n<=9;n++) { sum=1;int F=0; for (i=0;i<=n;i++) a[i]=i,sum*=(n+1-i); ans=0; for (t=1;t<=sum;t++) { now=0; for (i=0;i<=n;i++) now+=(i^a[i]); if (now>ans) ans=now,F=1,memcpy(wri[1],a,sizeof(a)); else if (now==ans) memcpy(wri[++F],a,sizeof(a)); next_permutation(a,a+n+1); } printf("%d %d\n",n,ans); for (int j=1;j<=F;j++) { for (i=0;i<=n;i++) printf("%d ",wri[j][i]); puts(""); } puts(""); } return 0; }

这里是AC程序：

#include
      
       
#include
       
         using namespace std; int a[25],f[1000005],x,k,i,n;long long ans=0; int main() { scanf("%d",&n); for (i=n;i;i--) if (!f[i]) { k=(int)(log2(i))+1;x=(1<

Codeforces Round #177 (Div. 2) 题解(三)