题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4818
题意：Alice 想要得到一个长度为 n 的序列，序列中的数都是不超过 m 的正整数，而且这 n 个数的和是 p 的倍数。Alice 还希望，这 n 个数中，至少有一个数是质数。Alice 想知道，有多少个序列满足她的要求。
好久以前在飞机上脑袋 AC 的一道傻逼题... 由于太困了当时没写就睡觉了... 大年三十随便写一发吧。
至少有一个数是质数即不管这个限制减去没有数是质数的情况。
\(f_{i,j}\) 表示考虑前\(i\) 个数，目前余数是\(j\) 的方案数，\(buc_i\) 表示当前决策一个余数是\(i\) 的数的方案数，转移如下：
\(f_{i,j}=\sum_{k=0}^{p-1}f_{i-1,(j-k)\ mod\ p}\times buc_k\)
发现是一个卷积的形式，由于数据范围非常小不用写 FFT（写了估计会变慢吧...），发现大力转移需要做\(n\) 次，快速幂优化即可。
时间复杂度\(p^2log_n\)。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define P 105 #define N 20000010 #define mod 20170408 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,p; int buc[P]; int pri[N>>3],cnt; bool pd[N]; void get_pri(int n) { pd[1]=1; for(int i=2;i<=n;i++) { if(!pd[i])pri[++cnt]=i; for(int j=1;j<=cnt&&i*pri[j]<=n;j++) { pd[i*pri[j]]=1; if(pri[j]%i==0)break ; } } for(int i=1;i<=n;i++) if(pd[i])buc[i%p]++; } int C[P]; void mul(int A[],int B[]) { memset(C,0,sizeof(C)); for(int i=0;i<p;i++) for(int j=0;j<p;j++)(C[(i+j)%p]+=(ll)A[i]*B[j]%mod)%=mod; for(int i=0;i<p;i++)A[i]=C[i]; } void quickmod(int a[],int b) { while(b) { if(b&1)mul(a,buc); b>>=1,mul(buc,buc); } } int f[P],g[P]; int main() { n=read(),m=read(),p=read(); get_pri(m); f[0]=g[0]=1; quickmod(f,n); memset(buc,0,sizeof(buc)); for(int i=1;i<=m;i++)buc[i%p]++; quickmod(g,n); printf("%d\n",(g[0]-f[0]+mod)%mod); } |
Comments | NOTHING