一道非常好的题,太菜了调了很久,细节非常多。
首先,将题意转化一下,由给定的两段都有的长度,可以组成多少种组合。
设dp[i]表示,长度为i的方案数。
那么有转移,$dp[i] = \sum_{j = 1}^{tot} dp[i-a[j]]$//tot为两段都有的元素个数,注意要去重
这里虽然可以用无限数量的背包思想,但是显然这样更好。
然后dp转移,60分。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<string,int> pii; const int N = 1e6+5; const int M = 2e5+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){/*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int vis[105],a[105],tot = 0; LL dp[N];//i拆分的方案数 int main() { int n;n = read(); int pr;pr = read(); for(rg int i = 1;i <= pr;++i) { int x;x = read(); vis[x] = 1; } int nf;nf = read(); for(rg int i = 1;i <= nf;++i) { int x;x = read(); if(vis[x]) a[++tot] = x; } sort(a+1,a+tot+1); int len = unique(a+1,a+tot+1)-a-1; tot = len; dp[0] = 1; for(rg int i = 1;i <= n;++i) { for(rg int j = 1;j <= tot;++j) if(i-a[j] >= 0) dp[i] = (dp[i]+dp[i-a[j]])%Mod; } printf("%lld\n",dp[n]); //system("pause"); }View Code
显然当n过大时,会超时。而且dp也存不下。
可以发现,块的大小最多为100,也就是代表一开始最多dp[100]。
那么我们可以矩阵快速幂加速。
构造初始矩阵f[0] ~ f[99]。那么右端矩阵即为f[1] ~ f[100]。
那么可以发现,除了第一行,其他行的转移矩阵就是1的对角线。即[i][i-1]的位置。
对于第一行 由$f[100] = \sum_{j = 1}^{tot} f[100-a[j]]$
我们可知,对于100-a[j]位置都应该是1,但是由于这里的横列相乘后,位置其实是相反的,那么对于100-a[j]的位置,就变成了a[j]位置,那么我们对所有a[j]位置都变1即可。
然后矩阵快速幂。应该是n-99次,因为左边到f[99]。
然后矩阵我们处理出了转移矩阵的k次,假定为res.
现在初始矩阵为ans.那么 ans * res 和 res * ans是不一样的。
这就和我们矩阵乘法的位置有关。//就是这里调了非常久。
所以最后应该是转移矩阵 * ans。然后答案就是ans[1][1]。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<string,int> pii; const int N = 1e6+5; const int M = 2e5+5; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){/*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int a[105],b[105]; struct Mat{ LL m[105][105]; Mat operator * (const Mat a)const{ Mat c;memset(c.m,0,sizeof(c.m)); for(rg int i = 1;i <= 100;++i) for(rg int j = 1;j <= 100;++j) for(rg int k = 1;k <= 100;++k) c.m[i][j] = (c.m[i][j]+(m[i][k]*a.m[k][j])%Mod)%Mod; return c; } }; LL f[105]; Mat quick_mi(Mat a,LL b) { Mat res;memset(res.m,0,sizeof(res.m)); for(rg int i = 1;i <= 100;++i) res.m[i][i] = 1; while(b) { if(b&1) res = res*a; a = a*a; b >>= 1; } return res; } int main() { LL n;n = read(); int pr;pr = read(); while(pr--){int x;a[x = read()] = 1;} int nf;nf = read(); while(nf--){int x;b[x = read()] = 1;} Mat ans;memset(ans.m,0,sizeof(ans.m)); for(rg int i = 1;i <= 100;++i) { if(a[i] && b[i]) ans.m[1][i] = 1; } for(rg int i = 2;i <= 100;++i) ans.m[i][i-1] = 1; f[0] = 1; for(rg int i = 1;i < 100;++i) { for(rg int j = 1;j <= 100;++j) if(a[j] && b[j] && i-j >= 0) f[i] = (f[i]+f[i-j])%Mod; } if(n < 100) printf("%lld\n",f[n]); else { Mat res;memset(res.m,0,sizeof(res)); for(rg int i = 1;i <= 100;++i) res.m[i][1] = f[100-i]; ans = quick_mi(ans,n-99); res = ans*res; printf("%lld\n",res.m[1][1]); } system("pause"); }View Code