1002 Build a tree（递归）
题目链接 HDU6121 Build a tree
#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("%lldn",ans);
continue;
}
init();
printf("%lldn",solve(1));
}
return 0;
}1006 Free from square（状压DP）
题目链接 HDU6125 Free from square
#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("%lldn",ans);
}
return 0;
}1010 Just do it （找规律、递推、Lucas、快速幂）
题目链接 HDU6129 Just do it
#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;
}
