luogu1762 题目描述：给定一个整数n，求杨辉三角形前n项对1000003取模后的结果。
输入格式：一行一个整数n，表示行数
输入格式：一行一个整数，表示答案
输入样例： 6
输出样例： 6
解析：杨辉三角形第n行第m列的数为\(C_{n-1}^{m-1}\)，要求前n行的偶数个数，就是求前n行的奇数个数，再用总数减去奇数的个数。 那么怎么算奇数的个数呢？就是算\(C_{n-1}^{m-1} mod 2 = 1\)的个数。 用lucas定理可知，这时(m-1)是(n-1)的子集，即(m-1)&(n-1) = m - 1 可以发现，答案就是\(\sum_{i=0}^{n-1}2^{i的二进制下1的个数}\) 这样，就可以直接数位DP，求出即可。
代码如下：
#include<cstdio> #include<cstring> #define ll long long using namespace std; const ll MOD = 1000003; ll n, pow[64], dp[64][64]; int bit[64], cnt; ll dfs(int pos, int lead, int limit, int sum) { //数位DP if (!pos) return pow[sum]; if (~dp[pos][sum] && limit && lead) return dp[pos][sum]; int len = limit ? 1 : bit[pos]; ll ans = 0; for (int i = 0; i <= len; ++ i) { if (!lead && i == 0) ans += dfs(pos - 1, lead, limit || i < len, sum); else ans += dfs(pos - 1, lead || i > 0, limit || i < len, sum + (i == 1)); ans %= MOD; } if (limit && lead) dp[pos][sum] = ans; return ans; } ll solve(ll x) { while (x) { bit[++ cnt] = x % 2; x /= 2; } memset(dp, -1, sizeof(dp)); return dfs(cnt, 0, 0, 0); } ll mul(ll x, ll y) { //由于n太大，直接乘会爆long long，所以要打快速乘 ll res = 0, base = x; if (x & 1ll) y >>= 1; else base >>= 1; while (y) { if (y & 1) res = (res + base) % MOD; base = (base + base) % MOD; y >>= 1; } return res; } int main() { scanf("%lld", &n); n --; pow[0] = 1; for (int i = 1; i < 64; ++ i) pow[i] = pow[i - 1] * 2 % MOD; printf("%lld", (mul(n + 1, n + 2) - solve(n) + MOD) % MOD); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9933559.html
相关资源：苏少版音乐一上《京剧锣鼓》课件