#include <bits/stdc++.h>
using namespace std;
const int N=15;
const int M=400;
const int K=105;
const int MOD=100000000;
int m, n;
int st[M];
int cnt;
long long dp[N][M];
int r[N];
bool check(int s1, int s2){
if (s2&s1) return false;
return true;
}
int count1(int x){
int res=0;
while(x){
res+=x&1;
x=x>>1;
}
return res;
}
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
r[i]=0;
for(int j=0;j<n;j++){
int x;
cin>>x;
if(x==1){
r[i]|=(1<<j);
}
}
}
cnt = 0;
for(int i=0;i<(1<<n);i++){
if ((i&(i<<1))==0){
st[cnt++]=i;
}
}
for (int i=0;i<N;i++)
for (int j=0;j<M;j++)
dp[i][j]=0;
for(int p=0;p<cnt;p++){
int s=st[p];
if((s&r[1])==s){
}
}
for (int i=2;i<=m;i++){
for (int p=0;p<cnt;p++){
if(dp[i-1][p]==0) continue;
for (int q=0;q<cnt;q++) {
int ns=st[q];
if((ns&r[i])!=ns) continue;
if (!check(st[p],ns)) continue;
dp[i][q] = (dp[i][q] + dp[i-1][p]) % MOD;
}
}
}
long long ans=0;
for (int j=0;j<cnt;j++){
ans=(ans+dp[m][j])%MOD;
}
cout<<ans<<'\n';
return 0;
}
#include<bits/stdc++.h>
#include<map>
using namespace std;
const int a=1005;
const int b=1005;
int c[a][b];
int d[a];
int e[2][b][a];
map<int,int> f;
int g;
int h[b],i[b*b],j[b*b],k[b*b],l;
void m(int n,int o,int p) {
l++;
j[l]=o;
k[l]=p;
i[l]=h[n];
h[n]=l;
}
int q(int r) {
if(f.find(r)==f.end()) {
f[r]=++g;
}
return f[r];
}
int main() {
freopen("polygon.in","r",stdin);
freopen("polygon.out","w",stdout);
int n,s,t;
cin>>n>>s>>t;
for(int u=1; u<=n; u++) {
cin>>d[u];
for(int v=1; v<=d[u]; v++) {
cin>>c[u][v];
q(c[u][v]);
}
}
memset(h,-1,sizeof(h));
for(int u=1; u<=n; u++) {
for(int v=1; v<=d[u]; v++) {
int w=q(c[u][v]);
for(int x=v+1; x<=d[u]&&x-v+1<=s; x++) {
int y=q(c[u][x]);
m(w,y,u);
}
}
}
while(t--) {
int r,z;
cin>>r>>z;
int aa=q(z);
memset(e,0,sizeof(e));
for(int u=1; u<=n; u++) {
for(int v=1; v<=d[u]; v++) {
if(c[u][v]!=1)continue;
for(int bb=v+1; bb<=d[u]&&bb-v+1<=s; bb++) {
int cc=q(c[u][bb]);
e[1][cc][u]=1;
}
}
}
if(r==1) {
bool dd=false;
for(int u=1; u<=n; u++) {
if(e[1][aa][u]) {
dd=true;
}
}
if(dd) {
cout<<"Yes"<<'\n';
} else {
cout<<"No"<<'\n';
}
continue;
}
int ee=1;
int ff=2*n+5;
if(r<ff) {
ff=r;
}
bool gg=false;
for(int hh=2; hh<=ff; hh++) {
int ii=ee^1;
memset(e[ii],0,sizeof(e[ii]));
for(int jj=1; jj<=g; jj++) {
for(int kk=1; kk<=n; kk++) {
if(!e[ee][jj][kk])continue;
for(int ll=h[jj]; ll!=-1; ll=i[ll]) {
int mm=j[ll];
int nn=k[ll];
if(nn==kk)continue;
e[ii][mm][nn]=1;
}
}
}
ee=ii;
if(hh==r) {
for(int u=1; u<=n; u++) {
if(e[ee][aa][u]) {
gg=true;
}
}
break;
}
}
if(r<=ff) {
if(gg) {
cout<<"Yes"<<'\n';
} else {
cout<<"No"<<'\n';
}
} else {
bool oo=false;
for(int u=1; u<=n; u++) {
if(e[ee][aa][u]) {
oo=true;
}
}
if(oo) {
cout<<"Yes"<<'\n';
} else {
cout<<"No"<<'\n';
}
}
}
return 0;
}
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=3000005;
int n,k,a[N],P[N],S[N],q[N];//P[i]=Σ(a[j]-1),S[i]=Σa[j],q:单调队列存下标
bool chk(int len){//判断是否存在长度len的窗口内每天都能吃到鱼
if(len==0)return true;
int h=0,t=0;
for(int i=1;i<=len;i++){//初始化窗口[1,len]的单调队列(按P递增)
while(h<t&&P[q[t-1]]>=P[i])t--;
q[t++]=i;
}
for(int L=1;L+len-1<=n;L++){//滑动窗口
int R=L+len-1;
if(L>1){//加入R,弹出过期下标
while(h<t&&P[q[t-1]]>=P[R])t--;
q[t++]=R;
while(h<t&&q[h]<L)h++;
}
int I=S[L-1]-S[max(0,L-k-1)];//[L-k,L-1]内能覆盖到L的鱼数
if(P[q[h]]+I>=P[L-1])return true;//minP+I>=P[L-1]即可行
}
return false;
}
int main(){
freopen("fish.in","r",stdin);
freopen("fish.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
S[i]=S[i-1]+a[i];
P[i]=P[i-1]+a[i]-1;
}
int l=0,r=n,ans=0;
while(l<=r){//二分答案
int m=(l+r)/2;
if(chk(m)){ans=m;l=m+1;}
else r=m-1;
}
printf("%d\n",ans);
return 0;
}
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 70005, LIM = 30000;
int n, k, opt;
int f[N];
bool prime[N];
int main() {
freopen("pile.in", "r", stdin);
freopen("pile.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> opt;
if (opt == 1) cin >> n;
else cin >> n >> k;
int mx = max(n, 2);
memset(prime, true, sizeof(bool) * (mx + 1));
prime[0] = prime[1] = false;
for (int i = 2; i * i <= mx; i++)
if (prime[i])
for (int j = i * i; j <= mx; j += i)
prime[j] = false;
int up = min(n, LIM);
for (int m = 2; m <= up; m++) {
int best = 0;
for (int a = 1; a <= m / 2; a++)
best = max(best, f[a] + f[m - a]);
f[m] = best + (prime[m] ? 1 : 0);
}
int ans = (n <= LIM) ? f[n] : (n - 1);
cout << ans << '\n';
if (opt == 2) cout << 1 << '\n';
return 0;
}