E. Liner vectors

E. Liner vectors

题意：

规定n位数 可以使得任意k位为1 其余为0 要求判断能否构造出n个不同的n位二进制数 满足任意一个数都不能有其他已构造出来的数亦或得到。

如果能构造出这n个二进制数按字典序输出符合条件最小的数 否则输出-1

思路：

如果n == k显然只能构造一个数 只有k=1时才满足其余都不行 

如果 k为偶数 肯定不能构造出n个 因为含相同个数1的两个二进制数 亦或 最后得到的数的二进制中肯定包含偶数个1  一个二进制肯定能由其他两个或几个亦或得到

如果k是奇数 要满足一个数不能由其他n-1个数亦或得到 就是要这n个数线性无关 对于k=3

0111                                                                      

1011                                                                           011

1101                                                                           101 

1110这个矩阵满秩是线性无关的 但如果k是偶数  例  110 如果按亦或操作是线性相关的不满足 

                                                                                                             0010011

                                                                                                             0100011

然后对于n 固定后k-1位为1 还有一位1可以放在前1到n-(k + 1)位 例：1000011 显然这几个数也是线性无关的 而这几个数与前k+1个数也是线性无关的 

 正好n个且字典序最小

#include
#include
#include<string> 
#include<set> 
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define m_p make_pair
#define pi acos(-1)
#define gcd(a, b) __gcd(a,b)
#define lcm(a, b) a/gcd(a,b)*b
using namespace std;
 
const int N = 1e6 + 5;
const double eps = 1e-4;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
//const ll mod = 1000003;
inline ll qpow(ll x, ll y, ll M){ll ans=1;while(y){if(y&1)ans=ans*x%M;x=x*x%M;y=y>>1;}return ans;}
string s;
mapchar, ll>>mp;
maptrk;
ll n, k;

void solve()
{
    cin >> n >> k;
    if(n == 1LL) cout << 1 << "\n";
    else if(n == k || k % 2 == 0) cout << -1 << "\n";
    else{
        ll x = (1LL << k) - 1LL;
        cout << x;
        ll num2 = 1LL << k;
        for(int i = k - 1; i >= 0; i--){
            ll xx = (num2 - 1LL) ^ (1LL << i);
            cout << " " << num2 + xx;
        }
        ll yy = (1LL << (k - 1LL)) - 1LL;
        for(int i = k + 1LL; i <= n - 1LL; i++){
            ll xx = 1LL << i;
            ll ans = xx ^ yy;
            cout << " " << ans;
        }
        cout << "\n";
    }
}    
 
signed main()
{
    IOS;
    //init();
    ll t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}
数学思维

相关

标签