水题解析——7的倍数
题面：
【题目名称】7的倍数
【时间限制】每个测试点300ms
【空间限制】128M
【题目描述】
给定一个各项均不相同且项数为n的正整数数列:A1,A2,A3,……,An.从中选取若干个数(至少一个),使这些数之和为7的倍数.求共有多少种不同的选法.
测试数据分为两类:
A类：数列由输入数据直接给出；
B类：给定k(k<=100000)个正整数：p1,p2,p3,……,pk.数列由通项公式：
An=p1^n+p2^n+p3^n+……+pk^n确定.
【输入格式】
第一行,两个整数n,k：其中n表示数列项数.若k=0,则表示该组数据为A类数据;若k>0,则表示该组数据为B类数据.
第二行,若为A类数据,则接下来有n个互不相同的正整数，其中第i个数表示数列的第i项;若为B类数据,则接下来有k个正整数:p1,p2,p3,…,pk.(具体含义见题目描述)
【输出格式】
一个非负整数,表示共有多少种选法.由于答案可能很大,请mod 1000000007后输出.
【样例输入1】
6 0
1 2 3 4 5 6
【样例输出1】
9
【样例输入2】
4 2
3 5
【样例输出2】
2
【数据范围与约定】
对于20%的数据，k=0，1<=n<=20；
对于60%的数据，k=0，1<=n<=100000；
对于另 40%的数据，1<=k<=10^5，1<=n<=10^18.
数据：
这题数据并没有什么特别之处，在此就不提供数据了。
题解：
20分算法：搜索
只处理A类数据.
- 很裸很裸的暴力搜索；
- 依次枚举每个数选与不选；
- 然后验证并计数；
- 时间复杂度O(2^n).
20分暴搜代码：
#include<cstdio>
#define mod 1000000007
int n,k,A[1100],cnt=0;
void dfs(int p,int num)
{
if(p>n)
{
cnt+=(num%7==0);
if(cnt>mod)
{
cnt-=mod;
}
return ;
}
dfs(p+1,num);
dfs(p+1,num+A[p]);
return ;
}
int main()
{
scanf("%d%d",&n,&k);//只处理A类数据;
for(int i=1;i<=n;i++)
{
scanf("%d",&A[i]);
}
dfs(1,0);//深搜;
printf("%d",cnt-1);//排除一个也不选的情况;
return 0;
}60分算法：背包
在爆搜的时候，我们讨论每个数选与不选的情况，这给人一种背包问题的感觉.事实上，这还真是个背包问题.
状态：f[i][j]表示从前i个数中选取若干个数，使它们之和mod 7得j的方案数。
那么我们的转移方程是：
f[i][j]=f[i-1][j]+f[i-1][(j-(A[i]%7)+7)%7]..
后面那一坨是什么意思？
举个例子，比如遇到A[i]%7==4时:
那么f[i][5]=f[i-1][5]+f[i-1][1],(注:(5-4+7)%7=8%7=1).
f[i][2]=f[i-1][2]+f[i-1][5],(注:(2-4+7)%7=5%7=5).
加7再mod 7是为了将减得的负的余数，转为正的.
当然我们还可以用滚动数组，优化空间复杂度.
具体实现参见： 60分背包代码：
#include<cstdio>
#define mod 1000000007
int n,k,f[2][7];
int main()
{
//仍然只处理A类数据;
scanf("%d%d",&n,&k);
f[0][0]=1;//表示余数为0的方案有1种;
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
x%=7;//直接取mod
for(int j=0;j<=6;j++)
{
f[i&1][j]=f[i&1^1][(j-x+7)%7];//余数为j的可以由余数为(j-x+7)%7的转化而来;
}//因为更新过程是一个环状的过程，不能像裸的背包那样原地更新覆盖，故采用滚动.
for(int j=0;j<=6;j++)
{
f[i&1][j]+=f[i&1^1][j];
f[i&1][j]%=mod;
}
}
printf("%d",f[n&1][0]-1);//排除一个也不选的情况;
return 0;
}100分算法：背包+矩阵乘法
不难发现：
- 数据很大
- 时间复杂度应该是O(log n)的,可能还会有常数
- 背包的转移方程只与A[i]%7的值有关，而这个总共只有7种情况
- 相同余数对应相同的转移方程
- 转移方程可以写成矩阵乘法的形式
- 对于A[i]我们只关心它们%7的值，而不关心其本身的大小
- 由费马小定理知，A[i]%7的余数呈周期变化，最小正周期<=6
- 根据这些我们已经可以写出一个O(7^4 * log n)的算法了
不过还有一些细节,这些会在100分代码中呈现:
#include<cstdio>
#define ll long long
#define mod 1000000007
ll n,r[10],xi[10],tmp[10],cnt[10];
/*
r[i]表示Ai mod 7的余数;
xi[i]表示在p[1~k]中mod 7余i的数的个数;
tmp[i]是一个临时变量,用处见后文;
cnt[i]表示在n个数中,mod 7余i的数的个数,是矩阵乘法的指数;
*/
ll A[10][10],ANS[10][10],C[10][10];
//矩阵:A--底数,ANS--答案,C--临时中转;
int k;
int main()
{
scanf("%I64d%d",&n,&k);
if(k==0)
{
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
cnt[x%7]++;
}
}//A类;
else
{
for(int i=1,x;i<=k;i++)
{
scanf("%d",&x);
xi[x%7]++;
}//记录pk数列中mod 7得i的有多少个;不记也可.
for(int i=0;i<=6;i++)
{
tmp[i]=1;
}
for(int i=1;i<=6;i++)
{
for(int j=0;j<=6;j++)
{
tmp[j]=tmp[j]*j%7;
r[i]=(r[i]+xi[j]*tmp[j])%7;
}
}//处理循环节1~6的情况;
int rr=n%6;
for(int i=1;i<=6;i++)
{
if(i<=rr)
{
cnt[r[i]]+=n/6+1;//利用循环的性质计数;
}
else
{
cnt[r[i]]+=n/6;//同上;
}
}
}
for(int i=0;i<=6;i++)
{
ANS[i][i]=1LL;
}//赋初始值;
for(int i=0;i<=6;i++)//讨论各个余数的情况;
{
for(int j=0;j<=6;j++)
{
for(int k=0;k<=6;k++)
{
A[j][k]=0;
}
}//清零底数;
for(int j=0;j<=6;j++)
{
A[j][j]+=1LL;
A[(j-i+7)%7][j]+=1LL;
}//构建矩阵;
for(;cnt[i];cnt[i]=cnt[i]>>1)
{
if(cnt[i]&1)
{
for(int s1=0;s1<=6;s1++)
{
for(int s2=0;s2<=6;s2++)
{
C[s1][s2]=0LL;
for(int s3=0;s3<=6;s3++)
{
C[s1][s2]=(C[s1][s2]+ANS[s1][s3]*A[s3][s2])%mod;
}
}
}
for(int s1=0;s1<=6;s1++)
{
for(int s2=0;s2<=6;s2++)
{
ANS[s1][s2]=C[s1][s2];
}
}
}//ANS=ANS*A%mod;
for(int s1=0;s1<=6;s1++)
{
for(int s2=0;s2<=6;s2++)
{
C[s1][s2]=0LL;
for(int s3=0;s3<=6;s3++)
{
C[s1][s2]=(C[s1][s2]+A[s1][s3]*A[s3][s2])%mod;
}
}
}
for(int s1=0;s1<=6;s1++)
{
for(int s2=0;s2<=6;s2++)
{
A[s1][s2]=C[s1][s2];
}
}//A=A*A%mod;
}//快速幂;
}
printf("%I64d",ANS[0][0]-1);//排除一个也不选的情况;
return 0;
} 至此这道水题就讲完了.