wordpress seo选项,推广seo是什么意思,网络促销策略,一个公司网站多少钱F-Lucky Pascal Triangle
issue是fw题解
下面代码TLE了#xff0c;但是此题数位dp的思想非常值得学习 Lucas的过程相当于把n,mn,mn,m在p进制下的每一位拿出来做组合数 Lucas(n,m,p)∏(nkmk)modp\text{Lucas}(n,m,p)\prod \dbinom {n_k}{m_k} \bmod pLucas(n,m,p)∏(mknk…F-Lucky Pascal Triangle
issue是fw题解
下面代码TLE了但是此题数位dp的思想非常值得学习 Lucas的过程相当于把n,mn,mn,m在p进制下的每一位拿出来做组合数
Lucas(n,m,p)∏(nkmk)modp\text{Lucas}(n,m,p)\prod \dbinom {n_k}{m_k} \bmod pLucas(n,m,p)∏(mknk)modp 本题需要求 ∑i1n∑j1i[(ij)mod70]\sum_{i1}^{n}\sum_{j1}^i[\dbinom {i}{j} \bmod 70] i1∑nj1∑i[(ji)mod70]
由于nk,mkn_k,m_knk,mk都小于7组合数不可能包含7的因此想让(nm)mod70\dbinom {n}{m}\bmod 70(mn)mod70 当且仅当∏(nkmk)mod70\prod \dbinom {n_k}{m_k} \bmod 7 0∏(mknk)mod70 即存在nkmkn_km_knkmk因为此时(nkmk)0\dbinom {n_k}{m_k}0 (mknk)0
#includebits/stdc.husing namespace std;
const int mod1e97;
using lllong long;
ll n;
int a[24];
int f[24][2][2][2];
int dfs(int u,int lim1,int lim2,int ok)
{if(u0) return ok;if(f[u][lim1][lim2][ok]!-1) return f[u][lim1][lim2][ok];int v1lim1?a[u]:6;f[u][lim1][lim2][ok]0;int ans0;for(int i0;iv1;i)for(int j0;j(lim2?i:6);j)ans(1ll*ansdfs(u-1,lim1(iv1),lim2(ij),ok|(ij)))%mod;return f[u][lim1][lim2][ok]ans;
}
int solve(ll x)
{memset(f,-1,sizeof f);int cnt0;while(x) a[cnt]x%7,x/7;return dfs(cnt,1,1,0);
}
int main()
{ios::sync_with_stdio(false);cin.tie();cout.tie(0);int Tc;cinTc;for(int ca1;caTc;ca){cinn;coutCase ca: solve(n)\n;}return 0;
}
