#include <bits/stdc++.h>
typedef long long LL; const int MOD = (int)1e9 + 7;
LL L,R,G,T;
int dp[62 + 1][2][2][2][2];
bool vis[62 + 1][2][2][2][2]; inline void add(int &a,int b) {
a += b;
if (a >= MOD) a -= MOD;
if (a < 0) a += MOD;
} int calc(int at,bool al,bool ar,bool bl,bool br) {
if (at == -1) {
return 1;
}
if (vis[at][al][ar][bl][br]) {
return dp[at][al][ar][bl][br];
} vis[at][al][ar][bl][br] = true;
int &ret = dp[at][al][ar][bl][br];
ret = 0; int l = L >> at & 1,
r = R >> at & 1,
x = (G ^ T) >> at & 1;
for (int a = 0; a < 2; ++ a) {
if (al && a < l) continue;
if (ar && a > r) continue;
int b = x ^ a;
if (bl && b < l) continue;
if (br && b > r) continue;
add(ret,calc(at - 1,al && a == l,ar && a == r,bl && b == l,br && b == r));
}
return ret;
} int work() {
if ((G ^ T) == 0) return (R - L + 1) % MOD;
memset(vis,false,sizeof(vis));
return ((R - L + 1) * 2 % MOD - calc(62,true,true,true,true) + MOD) % MOD;
} int main() {
int cas;
scanf("%d",&cas);
while (cas--) {
scanf("%I64d%I64d%I64d%I64d",&L,&R,&G,&T);
printf("%d\n",work());
}
}
GTW likes czf
从前，有两个人名叫GTW，DSY。一天，他们为了争夺DSY的妹子CZF，决定进行一次决斗。首先，CZF会给出一个区间l,l+1,l+2......rl,l+1,l+2......r，和两个数G,T。现在，CZF会在G,T两个数中随机一个数XX，在区间l,rl,r中随机一个数Y,进行一种特殊的运算@。CZF想要快速知道有多少数字可能会是答案。
然而GTW并不会做这道题，但是为了赢得CZF，他就来寻求你的帮助。
由于答案可能会很大，所以把最终的答案模1000000007。
我们规定运算X @ Y =((X and Y) or Y) xor X. ----------------------------------------------------------------------------------------------------------------------------------------------
给定一个长度为72的数a（a是山形的），求0~a-1中有多少个数是山形的。
http://codeforces.com/gym/100827 （E）
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <stdlib.h>
#include <sstream>
#include <assert.h>
#include <memory.h>
#include <complex> #include <time.h>
#pragma comment(linker, "/STACK:100000000")
using namespace std; #define mp make_pair
#define pb push_back
#define ll long long
#define sz(x) (int)(x).size()
#define fr(i,a,b) for(int i = (a);i <= (b);i++) int ri(){int x;scanf("%d",&x);return x;} ll dp[75][11][2][2];
string s; ll go(int pos,int lst,int up,int e)
{
if (pos == s.length())
return 1;
if (dp[pos][lst][up][e] != -1)
return dp[pos][lst][up][e];
ll res = 0;
int f = e ? s[pos] - '0' : 9;
int tmp = lst == 10 ? -1 : lst;
for(int i = 0;i <= f;i++)
{
if (up)
{
if (i >= tmp)
res += go(pos + 1,i,up,e & (i == f));
else
res += go(pos + 1,i,false,e & (i == f));
}
else
{
if (i <= tmp)
res += go(pos + 1,i,false,e & (i == f));
}
}
return dp[pos][lst][up][e] = res;
} int main()
{
//freopen("input.txt","rt",stdin);
//freopen("insider.in","rt",stdin);
//freopen("insider.out","wt",stdout); int T;
scanf("%d", &T);
while(T--)
{
cin >> s;
while(s.length() > 1 && s[0] == '0')
s = s.substr(1,s.length() - 1);
bool check = true;
int i;
for(i = 1;i < s.length();i++)
{
if (s[i] >= s[i - 1]);
else
break;
}
for(;i < s.length();i++)
if (s[i] > s[i - 1])
check = false;
if (check)
{
memset(dp,-1,sizeof(dp));
cout << go(0,10,1,1) - 1 << endl;
}
else
cout << -1 << endl;
} return 0;
}
------------------------------------------------------------------------------------------------------------------------------------------------
http://codeforces.com/problemset/problem/55/D
求一个区间内beautiful num的数量。（beautiful num:如果一个数能被它所有数位上的非0数整除，那么它就是一个beautiful num , 如12 ，15，而13不是）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
ll dp[20][2520][49] ;
int orm[2521] ;
int cnt ;
int bit[20] ; void init () {
for (int i = 1 ; i <= 2520 ; i ++) {
if (2520%i == 0) orm[i] = ++ cnt ;
}
} ll calc (int pos , int pre , int lcm , int welt ) {
if (pos == -1)
return pre%lcm==0 ;
if (welt == 0 && dp[pos][pre][orm[lcm]] != -1)
return dp[pos][pre][orm[lcm]] ;
int f = welt?bit[pos]:9 ; ll ret = 0 ;
for (int i = 0 ; i <= f ; i ++) {
int curpre = (pre*10+i)%2520 ;
int curlcm = lcm ;
if (i) curlcm = curlcm*i/__gcd(curlcm,i) ;
ret += calc (pos-1,curpre,curlcm,welt && i==f) ;
}
//cout << "pos = " << pos << " pre = " << pre << " lcm = " << lcm << " welt = " << welt << endl ;
//cout << "ret = " << ret << endl ;
if (welt == 0) dp[pos][pre][orm[lcm]] = ret ;
return ret ;
} ll work (ll x) {
int pos=0 ;
while (x) {bit[pos++]=x%10;x/=10;}
return calc(pos-1 , 0 , 1 , 1) ;
} int main () {
init () ;
int T ;
cin >> T ;
memset (dp , -1 , sizeof(dp)) ;
//cout << "cnt = " << cnt << endl ;
while (T --) {
ll l , r ;
cin >> l >> r ;
cout << work(r)-work(l-1) << endl ;
}
return 0 ;
}