日期计算以\(400\)年为周期，每\(400\)年都有恰好\(146097\)天。（\(146097=365 \times 400 +100-4+1\)）
预处理出\(400\)年内的情况，将年份模\(400\)即可快速得到答案。
几个简化代码的技巧：
对于格里高利历，以\(1200\)年\(1\)月\(1\)日为起始日，\(r\) 减去跳过的天数（\(2159351\)）。（\(2159351=1478\times1461+3-10\)）
(为什么要 \(+3\) 呢?因为从 \(1200\) 年后算法与儒略历不同，少算了闰年多的3天，再减去\(1582\)年\(10\)月少的 \(10\) 天，选择 \(1200\) 是因为刚好 \(400\)的倍数，且与 \(1582\)离得近)。
判断历法：\(r\leqslant 2299160\)即为儒略历 。
(\(2299160=1573\times1461+731+31+28+31+30+31+30+31+31+30+3\))
公元前xxx年视为 \(1−x\) 年。
记得开 long long
#include<bits/stdc++.h>
#define N 146097 //格里高利历400年的天数
#define int long
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int Q,n,year,month,day;
int d[N],m[N],y[N];
int md(int y,int m){ //格里高利历y年m月的天数
if(m==2) return y%4?28:(y%100?29:(y%400?28:29));
return (m==4||m==6||m==9||m==11)?30:31;
}
void pre(){
m[0]=d[0]=1;
for(int i=1;i<N;++i){
d[i]=d[i-1]+1,m[i]=m[i-1];y[i]=y[i-1];
if(d[i]>md(y[i],m[i])) ++m[i],d[i];
if(m[i]>12) m[i]=1,++y[i];
}
}//y[i],m[i],d[i]分别表示从0年1月1日经过i天的年月日
signed main(){
pre();
Q=read();
while(Q--){
n=read();
if(n>){ //格里高利历
}else{
year=n/1461*4-4712; //1461是儒略历4年的天数
n%=1461;
}
if(year+y[n]) printf("%d %d %lld\n",d[n],m[n],year+y[n]);
else printf("%d %d %lld BC\n",d[n],m[n],1-year-y[n]);
}
return 0;
}
考虑每一位，要么这一位被动物覆盖，要么这位不被动物覆盖，且这一位不需要饲料
。设符合的位的个数为 \(cnt\)，答案为 \(2^{cnt}-n\)。这道题卡 \(unsigned \ long\ long\) 可以开 __int128，也可以特判过 \(cnt\) 为 \(64\) 的情况。
if(k-cnt==64){
if(n) cout<<ull(-n)<<endl;
else cout<<"18446744073709551616"<<endl;
}
当然你不需要背下 \(18446744073709551616\) 来，只要先输出一个(unsigned long long)-1 再加上 \(1\) 就行了。
\(O(kn)\)
#include<bits/stdc++.h>
#define N 1000005
#define int __int128
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,c,k,cnt;
int a[N],p[N],q[N];
int b[N],flag[N];
void write(int x){
if(x>9) write(x/10);
putchar(x%10+'0');
}
signed main(){
n=read(),m=read(),c=read(),cnt=k=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i) p[i]=read(),q[i]=read(),b[p[i]]++;
for(int i=1;i<=n;++i){
int x=a[i];
int pos=0;
while(x){
if(x&1) flag[pos]=1;
x>>=1,pos++;
}
}
for(int i=0;i<=k;++i) if(!flag[i]&&b[i]) cnt--;
int ans=1;
for(int i=1;i<=cnt;++i) ans*=2;
write(ans-n);
return 0;
}
\(O(n)\)
先开一个数组 \(buc_j\) 表示是否有 \(a_i\) 的第 \(j\) 位上是 \(1\)。
又看到题目中保证 \(q_i\) 互不相同，所以一旦出现 \(p_i,q_i\) 满足 \(buc_{p_i}=0\)，那么这一位就不能选，因为当前买的饲料中必定没有 \(q_i\)。
不妨设剩下来 \(bit\) 位，那么这 \(bit\) 位既可以是 \(0\) 也可以是 \(1\)，共有 \(2^{bit}\) 种动物，减去现有的 \(n\) 种动物即可。
注意要特判 \(bit=64,n=0\) 的情况。读入量较大，建议写快读。
此外 \(buc\) 数组可以用 unsigned long long 变量代替，这样就做到了时间 \(O(n+m)\)，空间 \(O(1)\)。
非自己代码：
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define gc getchar()
inline ull rd(){
ull x=0; char s=gc;
while(!isdigit(s))s=gc;
while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=gc;
return x;
} ull n,m,c,k,ans,lim,hv;
int main(){
n=rd(),m=rd(),c=rd(),k=rd();
for(int i=1;i<=n;i++)hv|=rd(); // 统计每个位是否有 1
for(int i=1;i<=m;i++)lim|=1ull<<rd(),rd(); // 统计有限制的位
for(int i=0;i<k;i++)ans+=!((lim>>i)&1)||((hv>>i)&1); // 如果当前位有 1, 或者没有限制，那么都可以选
if(ans==64&&!n)puts("18446744073709551616");
else cout<<(ans==64?-n:(1ull<<ans)-n)<<endl;
return 0;
}