hdu 4507 吉哥系列故事——恨7不成妻

本文主要是介绍hdu 4507 吉哥系列故事——恨7不成妻，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

吉哥系列故事——恨7不成妻

题意

一个正整数和 $7$ 有关当且仅当满足以下条件之一：

• 数位中某一位是 $7$
• 数位和能被 $7$ 整除
• 这个整数能被 $7$ 整除

统计 $[l,r]$ 内所有和 $7$ 无关 的数字的 平方和

思路

这道题需要一点思维。我们先来看一个例子：

如果我们现在处理枚举 $pos$ 位为 $p$，低 $pos-1$ 位的结果已经处理完了，在当前限制下，低 $pos-1$ 的与 $7$ 无关的数有：$x_1,x_2,x_3$ 三个的话，那么它们的平方和应该是：$x_1^2+x_2^2+x_3^2$，现在我们要加上 $p$ 的贡献，就是将 $p$ 拼接上去，$p$ 这一位的值是 $p\cdot 10^{pos-1}$，与 $x_1$ 拼接成：$p{x}_1$，有：$(p{x}_1{)}^2=(p\cdot 10^{pos-1}+x_1{)}^2=(p\cdot 10^{pos-1}{)}^2+x_1^2+2\cdot x1\cdot (p\cdot 10^{pos-1})$
其实这里就是一个完全平方公式。

那么我们转移就可以通过维护更低位的平方和 $s_2$，符合条件的数有多少个 $cnt$，符合条件的数的和 $s_1$，三种信息。

转移就可以写成：
$s_2\prime =s_2+2\cdot s_1\cdot p\cdot 10^{pos-1}+cnt\cdot (p\cdot 10^{pos-1}{)}^2$
$s_1\prime =s_1+cnt\cdot p\cdot 10^{pos-1}$
$cnt\prime =cnt$

我们可以用 $dp[pos][r_1][r_2]$ 来表示 $pos$ 个全变化位，$r_1$ 为当前数位和模 $7$ 的余数，$r_2$ 为当前数模 $7$ 的余数条件下的信息。

搜到最底层时所有的位已经确定，所以节点只有一个信息 $cnt=1$ 返回。
$cnt$ 初始化为 $-1$ 是为了记忆化，这里的 $Z$ 类型当成是一个会自动取模的 $longlong$ 就可以

时间复杂度：$O(len\times 7\times 7)$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3e;
const long long INFLL=1e18;typedef long long ll;template<class T>
constexpr T power(T a, ll b){T res = 1;while(b){if(b&1) res = res * a;a = a * a;b >>= 1;}return res;
}constexpr ll mul(ll a,ll b,ll mod){ //快速乘，避免两个long long相乘取模溢出ll res = a * b - ll(1.L * a * b / mod) * mod;res %= mod;if(res < 0) res += mod; //误差return res;
}template<ll P>
struct MLL{ll x;constexpr MLL() = default;constexpr MLL(ll x) : x(norm(x % getMod())) {}static ll Mod;constexpr static ll getMod(){if(P > 0) return P;return Mod;}constexpr static void setMod(int _Mod){Mod = _Mod;}constexpr ll norm(ll x) const{if(x < 0){x += getMod();}if(x >= getMod()){x -= getMod();}return x;}constexpr ll val() const{return x;}explicit constexpr operator ll() const{ return x; //将结构体显示转换为ll类型： ll res = static_cast<ll>(OBJ)}constexpr MLL operator -() const{ //负号，等价于加上ModMLL res;res.x = norm(getMod() - x);return res;}constexpr MLL inv() const{assert(x != 0);return power(*this, getMod() - 2); //用费马小定理求逆}constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用return *this;}constexpr MLL& operator += (MLL rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLL& operator -= (MLL rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLL& operator /= (MLL rhs) & {return *this *= rhs.inv();}friend constexpr MLL operator * (MLL lhs, MLL rhs){MLL res = lhs;res *= rhs;return res;}friend constexpr MLL operator + (MLL lhs, MLL rhs){MLL res = lhs;res += rhs;return res;}friend constexpr MLL operator - (MLL lhs, MLL rhs){MLL res = lhs;res -= rhs;return res;}friend constexpr MLL operator / (MLL lhs, MLL rhs){MLL res = lhs;res /= rhs;return res;}friend constexpr std::istream& operator >> (std::istream& is, MLL& a){ll v;is >> v;a = MLL(v);return is;}friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){return os << a.val();}friend constexpr bool operator == (MLL lhs, MLL rhs){return lhs.val() == rhs.val();}friend constexpr bool operator != (MLL lhs, MLL rhs){return lhs.val() != rhs.val();}
};const ll mod = 1e9 + 7;
using Z = MLL<mod>;struct node{Z cnt; //限制条件下与7无关的数字数量Z s1; //与7无关的数字的和Z s2; //与7无关的数字平方和node(ll cnt = -1, ll s1 = 0, ll s2 = 0): cnt(cnt), s1(s1), s2(s2) {}//cnt 初始化为 -1 是等价于memset的操作
};node dp[20][8][8];
int num[20];
Z ten[20];node dfs(int pos, int r1, int r2, bool limit){ //r1：当前数位和模7  r2：当前数模7if(!pos) return (r1 && r2 ? node(1) : node(0));if(!limit && dp[pos][r1][r2].cnt != -1) return dp[pos][r1][r2];node res(0);int up = (limit ? num[pos] : 9);fore(i, 0, up + 1){if(i == 7) continue;node nxt = dfs(pos - 1, (r1 + i) % 7, (r2 * 10 + i) % 7, limit && i == up);res.cnt += nxt.cnt;res.s1 += nxt.cnt * i * ten[pos - 1] + nxt.s1;res.s2 += nxt.s2 + nxt.cnt * i * i * ten[pos - 1] * ten[pos - 1];res.s2 += 2 * nxt.s1 * i * ten[pos - 1];}if(!limit) dp[pos][r1][r2] = res;return res;
}Z solve(ll x){int len = 0;while(x){num[++len] = x % 10;x /= 10;}return dfs(len, 0, 0, true).s2;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);ten[0] = 1;fore(i, 1, 19) ten[i] = ten[i - 1] * 10;int t;std::cin >> t;while(t--){ll l, r;std::cin >> l >> r;Z ans = solve(r) - solve(l - 1);std::cout << ans << endl;}return 0;
}

这篇关于hdu 4507 吉哥系列故事——恨7不成妻的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---