---恢复内容开始---
题目大意：
求 1, 2, ..., n 有多少个长为 m 的子序列 a，
满足
a1 = 1,am = n
∀i, ai+1 − ai ≥ k
保证这样的子序列存在。只需判断方案数的奇偶性。数据有 T 组。 n, m, k ≤ 109 , T ≤ 2 × 106 .
//dfs枚举集合 //复杂度预估 O(T*2^n) //不用数组 得分30 //针对前6个点 #include<cstdio> #include<cstdlib> using namespace std; int t,n,m,k; int sum; void dfs(int pos,int x) { if(pos==m) { if(x==n) sum=(sum+1)%2 return ; } for(int i=x+k;i<=n;i++) dfs(pos+1,i); } int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); sum=0; dfs(1,1); if(sum) printf("Yes "); else printf("No "); } return 0; }
对于第8个点
{ scanf("%d%d%d",&n,&m,&k); if(m==2) printf("Yes "); else if(m==3) { sum=n-(k<<1); if(sum%2==1) printf("Yes "); else printf("No "); } else { sum=0; dfs(1,1); if(sum) printf("Yes "); else printf("No "); } }
//2记忆化
//dfs->dp //f[i][j]表示第i步，位置为j //因为状态转移方程中的k为变量，所以还是得分k的大小来dp //f[k][i][j] // 55 分
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int tt,nn,mm,kk;
int f[203][203][203];//1:true
inline int read()
{
int x=0;char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return x;
}
int dfs(int n,int m,int k)
{
if(f[k][m][n]!=-1) return f[k][m][n];
if(m==1) return f[k][m][n]=0;
if(m==2 )
if(n>k) return f[k][m][n]=1;
else return f[k][m][n]=0;
int s=k ,t=n-k*(m-2),as=0;
for(int i=s;i<=t;i++)
as=(as+dfs(n-i,m-1,k))%2;
return f[k][m][n]=as;
}
int main()
{
tt=read();
memset(f,-1,sizeof(f));
for(int i=1;i<=tt;i++)
{
nn=read(),mm=read(),kk=read();
if(mm==2) printf("Yes ");
else if(mm==3)
{
int sum=nn-(mm-1)*kk;
if(sum%2!=0) printf("Yes ");
else printf("No ");
}
else if( dfs(nn,mm,kk) ) printf("Yes ");
else printf("No "); }
return 0;
}
90分算法（n,m,k<=5000）
推式子。
注意到第二条约束与 a 的差分序列有关，考虑统计差分序列 bi = ai+1 − ai。
序列 b 需要满足
∀i, bi 是 [k, n] 上的整数
∑bi = n − 1
由于 a1 = 1 已确定，可以发现所有满足以上约束的长为 m − 1 的序列 b 与原来的序列 a 一一对应。
有限项的正整数序列的和确定时，其方案数可以用隔板法计 算，
所以构造 ci = bi − (k − 1) 来去除第一条约束，
序列 c 满足
∀i, ci 是正整数
∑m−1 ci = n − 1 − (m − 1)(k − 1)
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int t,nn,mm,kk; struct node {//m=m-2 int id,n,m;//n=n-2-(m-1)(k-1) bool operator < (const node & o) const { if(n!=o.n) return n<o.n; else return m<o.m; } }ask[2000003]; bool ans[2000003],f[5003]; int main() { scanf("%d",&t); for(int i=0;i<t;i++) scanf("%d %d %d",&nn,&mm,&kk), ask[i].n =nn-2-(mm-1)*(kk-1),ask[i].m =mm-2,ask[i].id =i; sort(ask,ask+t); int nw=0,nwn=1; nn=ask[nw].n ; f[0]=true; while(nw<t) { for(int i=nwn;i<=nn;i++) for(int j=i;j>=0;j--) f[j]^=f[j-1]; nwn=nn+1; while(ask[nw].n ==nn) ans[ask[nw].id ]=f[ask[nw].m ],nw++; nn=ask[nw].n ; } for(int i=0;i<t;i++) if(ans[i]) printf("Yes "); else printf("No "); return 0; }
100分算法
（解决两个1e9的超大点）
由 Lucas 定理，( n k ) ≡ 1 (mod 2)
当且仅当二进制下 k 的各 位都不大于 n 的对应位，即 n and k = k，
其中 and 为二进制按 位与。 复杂度：O(T)。
#include <cstdio> #include <cstdlib> using namespace std; int t,n,m,k; int main () { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); int a=n-(m-1)*(k-1)-2; int b=m-2; if((a&b)==b) printf("Yes "); else printf("No "); } return 0; }