1002 Build a tree（递归）
有一棵n个点的有根树，标号为0到n-1，i号点的父亲是\(\lfloor\frac{i-1}{k}\rfloor\)号点，求所有子树大小的异或和。\(1\leq n,k\leq10^{18}\)。
找出n所在的链，然后从根开始递归处理。
k=1的时候特判，1异或到n，每4个异或起来为0。
#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;
}
1006 Free from square（状压DP）
不大于n的所有正整数中选出至少1个且至多k个使得乘积不包含平方因子，对\(10^9+7\)取模。\(1\leq n,k\leq 500\)。
因为500内全部质因子没法直接状压。所以只把小于根号n的质因子状压起来，只有8个。
将大于根号n的质数划分为不同组，每组包含它们各自的倍数，每个组只能选1个数。且前8个质数每个在选出来的数的因子中最多出现一次。这是一次背包。
1~n中不包含平方因子且不包含大于根号n的质因子的数，做01背包，也要求前8个质数都最多出现一次。
f[i][j][k]表示前i组中选j个数，包含的质因子状态为k的方案数
dp[i][j][k]表示前i个数选j个，包含的质因子状态为k的方案数
再把两个背包合并起来。
f计算成前缀和，即f[i][j][k]表示选不超过j个数的方案数。
最后答案还要减去1,因为不能两个都选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;
}
1010 Just do it （找规律、递推、Lucas、快速幂）
有一个长度为n的整数序列\({a_n}\)，对其做m次前缀异或和，求最终的序列。\(1\leq n\leq2\times10^5,1\leq m\leq10^9,0\leq a_i\leq2^{30}-1\)。
法1.
i次变换第j个数是\(f[i][j]\)，那么f[i][j]=f[i][j-1]^f[i-1][j]（i>0,j>0），a[i]对f[x][y]有贡献当且仅当从f[1][i]走到f[x][y]有奇数条非降路径，也就是C（x-1+y-i,y-i）%2为1。由Lucas定理知C(n,m)%2为1当且经当(n&m)==m。计算出f[m][n]，f[m][1..n-1]就是对应错位的a[i]异或起来。当有贡献的a[i]不多时，就不会达到\(O(n^2)\)。
也可以打表找规律。
法2.
既然有递推式f[i][j]=f[i][j-1]^f[i-1][j]，那么就可以：
f[i][j]=f[i][j-2]f[i-2][j]，...，f[i][j]=f[i-2x][j]f[i-2x][j]。
然后用快速幂的思想做。
#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;
}