AcWing 1086 恨7不成妻 题解（动态规划—DP—数位DP） （困难）

原题传送门

#include

using namespace std;

typedef long long ll;

const int N = 19;//long long 的最大值9.22e18
const int P = 1e9 + 7;

int power7[N + 1];//10^i%7
int power10[N + 1];//10^i%P

struct Node{
	int s0, s1, s2;
}f[N + 1][10][7][7];

int mod(ll x, int y){
	return (x % y + y) % y;
} 

void init(){
	for(int i = 0; i <= 9; i ++ ){
		if(i == 7) continue;
		auto &v = f[1][i][i % 7][i % 7];
		v.s0 ++ ;
		v.s1 += i;
		v.s2 += i * i;
	}
	ll power = 10;//10^(i - 1)
	for(int i = 2; i <= N; i ++ , power *= 10){
		for(int j = 0; j <= 9; j ++ ){
			if(j == 7) continue;
			for(int a = 0; a < 7; a ++ ){
				for(int b = 0; b < 7; b ++ ){
					for(int k = 0; k <= 9; k ++ ){
						if(k == 7) continue;
						auto &v1 = f[i][j][a][b];
						auto &v2 = f[i - 1][k][mod(a - j * power, 7)][mod(b - j, 7)];
						// 1 + 1 + ... + 1  // t times
						// = t
						v1.s0 += v2.s0 % P;
						// jA1 + jA2 + ... + jAt
					    // = (j * 10 ^ (i - 1) + A1) + ...  // // think of f[i][j]
						 // = j * 10 ^ (i - 1) * t + (A1 + A2 + ... + At)
						v1.s1 += (j * (power % P) % P * v2.s0 + v2.s1) % P;
						// (jA1) ^ 2 + (jA2) ^ 2 + ... + (jAt) ^ 2
                        // = (j * 10 ^ (i - 1) + A1) ^ 2 + ...
                        // = (j * j * 10 ^ (i - 1) * 10 ^ (i - 1) + 2 * j * 10 ^ (i - 1) * A1 + A1 * A1) + ...
                        // = (j * j * 10 ^ (i - 1) * 10 ^ (i - 1) * t + 
                        //    2 * j * 10 ^ (i - 1) * (A1 + A2 + ... + At) + 
                        //    (A1 * A1 + A2 * A2 + ... + At * At)
						
						v1.s2 += (j * j * (power % P) % P * (power % P) % P * v2.s0 + 
								  2 * j * (power % P) % P * v2.s1 + v2.s2) % P;
								  
						v1.s0 %= P;
						v1.s1 %= P;
						v1.s2 %= P;
					}
				}
			}
		}
	}
	power7[0] = 1;
	for(int i = 1; i <= N; i ++ ){
		power7[i] = power7[i - 1] * 10 % 7;
	}
	
	power10[0] = 1;
	for(int i = 1; i <= N; i ++ ){
		power10[i] = power10[i - 1] * 10ll % P;
	}
} 

Node sum(int i, int j, int a, int b){
	int s0 = 0, s1 = 0 , s2 = 0;
	for(int x = 0; x < 7; x ++ ){
		for(int y = 0; y < 7; y ++ ){
			if(x != a && y != b){
				auto &v = f[i][j][x][y];
				s0 = (s0 + v.s0) % P;
				s1 = (s1 + v.s1) % P;
				s2 = (s2 + v.s2) % P;
			}
		}
	}
	return {s0, s1, s2};
}

ll dp(ll n){
	if(!n) return 0;
	
	ll x = n;
	vectornum;
	while(x) num.push_back(x % 10), x /= 10;
	
	ll res = 0;
	ll last_a = 0, last_b = 0;
	int i = num.size() - 1;
	while(i >= 0){
		int x = num[i];
		for(int j = 0; j < x; j ++ ){
			if(j == 7) continue;
			int a = mod(-last_a * power7[i + 1], 7);
			int b = mod(-last_b, 7);
			auto v = sum(i + 1, j, a, b);
			// (last_ajA1) ^ 2 + (last_ajA2) ^ 2 + ... + (last_ajAt) ^ 2
            // = (last_a * 10 ^ (i + 1) + jA1) ^ 2 + ...
            // = last_a * last_a * 10 ^ (i + 1) * 10 ^ (i + 1) + 2 * last_a * 10 ^ (i + 1) * A1 + A1 * A1
            // = last_a * last_a * 10 ^ (i + 1) * 10 ^ (i + 1) * t +
            //   2 * last_a * 10 ^ (i + 1) * (A1 + A2 + ... + At) +
            //   (A1 * A1 + A2 * A2 + ... + At * At)
			res = (res +
					(last_a % P) * (last_a % P) % P * power10[i + 1] % P * power10[i + 1] % P * v.s0 +
					 2 * last_a % P * power10[i + 1] % P * v.s1 + 
					 v.s2) % P;
		}
		if(x == 7) break;
		last_a = last_a * 10 + x;
		last_b += x;
		
		i -- ;
	}
	if(i == -1 && last_a % 7 && last_b % 7) {
		res = (res + (n % P) * (n % P)) % P;
	}
	return res;
} 

ll solve(ll l, ll r){
	return mod(dp(r) - dp(l - 1), P);
}

int main()
{
	int T;
	cin>>T;
	init();
	while(T -- ){
		ll l, r;
		cin>>l>>r;
		cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711868.html