【省选模拟】这道题（数位DP）（容斥）（组合数学）

【省选模拟】这道题（数位DP）（容斥）（组合数学）

#include#define cs constusing namespace std;cs int Mod = 1e9 + 7;int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }int mul(int a, int b){ return 1ll * a * b % Mod; }int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }void Add(int &a, int b){ a = add(a, b); }void Mul(int &a, int b){ a = mul(a, b); }void Dec(int &a, int b){ a = dec(a, b); }cs int N = 550, M = 15; int n, D, inv[M], C[N][N][M], pre[N][N][M], suf[N][N][M], good[N];struct atom{ vector G; atom(){ G.clear(); } void input(){ static char S[N*10]; scanf("%s",S); int len=strlen(S); for(int i=len-1; ~i; i--) G.push_back(S[i]-'0'); } int operator % (cs int &b){ int as = 0; for(int i=(int)G.size()-1;~i;i--) as=(as*10+G[i])%b; return as; } void operator /= (cs int &b){ for(int i=(int)G.size()-1,x=0;~i;i--){ int now=x*10+G[i]; x=now%b; G[i]=now/b; } while(G.size()&&G.back()==0) G.pop_back(); } bool iszero(){ return G.empty(); }};struct num{ vectorG; num(){ G.clear(); } void reset(){ G.clear(); } void input(){ atom T; T.input(); while(!T.iszero()) G.push_back(T%D), T/=D; } void minus(){ --G[0]; for(int i=0; i<(int)G.size()-1; i++){ if(G[i]<0) G[i]+=D,--G[i+1]; } if(!G.back()) G.pop_back(); } void inc(){ ++G[0]; G.push_back(0); for(int i=0; i<(int)G.size(); i++){ if(G[i]>=D) G[i]-=D,++G[i+1]; } if(!G.back()) G.pop_back(); } num operator + (cs num &A) cs{ num B; int deg=max(A.G.size(),G.size()); B.G.resize(deg); for(int i=0; ii?G[i]:0)+((int)A.G.size()>i?A.G[i]:0); B.G.push_back(0); for(int i=0; i=D) B.G[i]-=D, ++B.G[i+1]; if(!B.G.back()) B.G.pop_back(); return B; } int fnd(int x){ return (int)G.size()>=x?G[x-1]:0; } int len(){ return G.size(); } int val(){ int as=0; for(int i=G.size()-1;~i;i--)as=add(mul(as,D),G[i]); return as; }}; num L[M], R[M];num dnw;int work(){ static int dp[2][M],nxt[2][M],coef[N]; memset(coef,0,sizeof(coef)); memset(nxt,0,sizeof(nxt)); nxt[1][0]=1; for(int i=1; i<=510; i++){ memcpy(dp,nxt,sizeof(dp)); memset(nxt,0,sizeof(nxt)); for(int x=0; x0) Add(nxt[0][x+y],mul(trs,pre[i][now-1][y])); if(now+1=dnw.len()) Add(coef[x+y],mul(trs,suf[i][now+1][y])); } Add(nxt[0][x+y],mul(dp[0][x],C[i][now][y])); Add(nxt[1][x+y],mul(dp[1][x],C[i][now][y])); if(i==dnw.len()) Add(coef[x+y],mul(dp[1][x],C[i][now][y])); } } } int v=dec(0,dnw.val()), as=0; for(int x=0,c=1; x=0; d--) for(int j=0; j>i&1) ++t,dnw=dnw+R[i]; else dnw=dnw+L[i]; dnw.inc(); if(t&1) Dec(ans,work()); else Add(ans,work()); } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。