「2017 Multi-University Training Contest 7」2017多校训练7

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k;
int t,D;
ll f[64],siz[64],tot[64];
void init(){
    D=1;
    for(ll c=n-1;c;c=(c-1)/k)f[D++]=c;
    reverse(f+1,f+D);
    siz[0]=tot[0]=1;
    for(ll i=1,j=k;i<=D;++i,j*=k){
        siz[i]=siz[i-1]+j;
        tot[i]=(k&1?tot[i-1]:0)^siz[i];
    }
}
ll solve(int d){
    if(d==D)return 1;
    ll l=f[d]-f[d-1]*k-1;
    ll r=k-l-1;
    ll ans=n;
    if(l&1)ans^=tot[D-d-1];
    if(r&1)ans^=tot[D-d-2];
    n-=siz[D-d-1]*l+siz[D-d-2]*r+1;
    return ans^solve(d+1);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        if(k==1){
            ll ans=0;
            for(ll i=n/4*4;i<=n;++i)
                ans^=i;
            printf("%lld\n",ans);
            continue;
        }
        init();
        printf("%lld\n",solve(1));
    }
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define r(i,l,r,d) for(int i=(l);i<(r);i+=(d))
#define rep(i,l,r) for(int i=(l);i<(r);++(i))
#define add(x,y) x=(x+y)%M
const ll M=1e9+7;
const int N=515;
using namespace std;
int t,n,m;
ll dp[2][N][N];
ll f[2][N][N];
int p[N],cnt;//质数
bool isprime[N];
int s[N];//i中包含的质因子
int c;//第一个平方大于N的质数的下标
bool nofree[N];
void init() {
    mem(isprime,1);
    rep(i,2,N) if(isprime[i]) {
        p[cnt++]=i;
        if(i*i<N)c=cnt;
        r(j,i,N,i) isprime[j]=false;
    }
    rep(i,2,N) rep(j,0,cnt) if(i%p[j]==0) {
        if(j<c && (i/p[j])%p[j]) s[i]|=(1<<j);
        else {
            nofree[i]=true;
            break;
        }
    }
}
int main() {
    init();
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        mem(dp,0);
        mem(f,0);
        dp[0][0][0]=f[0][0][0]=1;

        rep(i,1,n+1)if(!nofree[i]) {
            rep(j,0,m+1) rep(k,0,1<<c) {
                add(dp[1][j][k],dp[0][j][k]);//不选i
                if(j<m && !(k&s[i]))
                    add(dp[1][j+1][k|s[i]],dp[0][j][k]);//选i
            }
            rep(j,0,m+1) rep(k,0,1<<c) dp[0][j][k]=dp[1][j][k],dp[1][j][k]=0;
        }
        rep(i,c,cnt) { //前i个平方大于N的质数
            rep(j,0,m+1) rep(k,0,(1<<c)) { //取j个，含有因子的状态为k
                add(f[1][j][k],f[0][j][k]);//不选p[i]的倍数
                if(j<m && f[0][j][k])
                    for(int l=1; p[i]*l<=n; ++l) //取p[i]的l倍
                        if(!nofree[l] && !(k&s[l])) add(f[1][j+1][k|s[l]],f[0][j][k]);
            }
            rep(j,0,m+1) rep(k,0,1<<c) f[0][j][k]=f[1][j][k],f[1][j][k]=0;
        }
        rep(i,0,m) rep(j,0,1<<c) add(f[0][i+1][j],f[0][i][j]);

        ll ans=M-1;
        rep(i,0,m+1) rep(j,0,1<<c) if(dp[0][i][j])
            rep(k,0,1<<c) if(!(k&j))
                add(ans,dp[0][i][j]*f[0][m-i][k]%M);
        printf("%lld\n",ans);
    }
    return 0;
}

#include <bits/stdc++.h>
const int N=200001;
using namespace std;
int t,n,m;
int ans[N],a[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		memset(ans,0,sizeof ans);
		for(int i=0;i<n;++i)
			scanf("%d",a+i);
		for(int i=0;i<n;++i)
			if(((m-1+i)&i) == i)//第i+1项中a[1]的系数为C(m-1+i,i)
				for(int j=i;j<=n;++j)//a[j-i+1]对第j项有贡献
					ans[j]^=a[j-i+1];
		for(int i=0;i<n;++i)
			printf("%d%c",ans[i],i==n-1?'\n':' ');
	}
	return 0;
}

#include <bits/stdc++.h>
int t,n,m;
int a[200001];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;++i)
			scanf("%d",a+i);
		for(int k=1;m;m>>=1,(k<<=1))
			if(m&1)
			for(int j=k;j<n;++j)
				a[j]^=a[j-k];
		for(int i=0;i<n;++i)
			printf("%d%c",a[i],i==n-1?'\n':' ');
	}
	return 0;
}