ARC058 E

ARC058 E

题意：

解法：

d[i][2][2][2][j]
长度为i,
是否满足条件1
是否满足条件2
是否满足条件3
当前和为j的方案数.对于长度为i的合法子数组,
还可以在左右两边添加n-i个数,
用组合数学计算一下贡献就行了,
但是深入思考之后发现这样会重复计算,
因为左右两边随便放可能也会组成满足条件的方案.---正着做不好计算,考虑反过来计算:
用总方案数减去不合法方案数,
总方案数显然为10^n.如何计算不合法方案数:
令d[i][s]表示长度为i的序列,末尾状态为s的方案数,
其中s需要不满足题目条件,
s存储的是[x,w-1]的每个数,
存储方法为:
假如末尾插入一个4,那么表示为1000,
即长度为4的二进制串,第4位为1,其他位置为0.
假如末尾再插入一个3,那么表示为1000100,
即右边插入一个3.
因为X+Y+Z<=17,因此二进制串最多17位.dp转移只需要保证任何时刻末尾都不满足条件即可.

code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=2e6+5;
const int mod=1e9+7;
int d[44][(1<<17)+5];
int n,X,Y,Z;
void solve(){cin>>n>>X>>Y>>Z;int limit=0;limit|=1;limit<<=X-1;limit<<=1;limit|=1;limit<<=Y-1;limit<<=1;limit|=1;limit<<=Z-1;//int tot=1;for(int i=1;i<=n;i++)tot=tot*10%mod;//int ma=(1<<(X+Y+Z))-1;d[0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=ma;j++){//枚举当前状态if(!d[i][j])continue;for(int x=1;x<=10;x++){//枚举末尾的数int nt=j;nt<<=1;nt|=1;nt<<=x-1;nt&=ma;//防止左边数位溢出if((nt&limit)==limit)continue;//不合法d[i+1][nt]=(d[i+1][nt]+d[i][j])%mod;}}}for(int j=0;j<=ma;j++){if((j&limit)==limit)continue;tot=(tot-d[n][j])%mod;}tot=(tot%mod+mod)%mod;cout<<tot<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);solve();return 0;
}