[ICPC2016Dalian Onsite]官方题解 作者: rin 时间: November 6, 2016 分类: Algo [PDF版](http://pan.baidu.com/s/1bpkkoTD) > 添加 `-D__STDC_FORMAT_MACROS`以支持`PRId64` #Problem A Wrestling Match ##提交情况:170/434 ##解题思路 本题做法比较随意,此处说两种: 1. 读入数据,建好图以后,以每一个点为开始遍历的起始节点,搜索整个图,在搜索的过程中判断是否出现冲突 2. 用并查集维护题目中所谓『好选手』以及『坏选手』的关系,在建立并查集的过程中,就可判断冲突 总的来说,第2种做法需要处理的特殊情况较少,并且计算量照第1种做法少,所以标程采用第2种做法。 ##标准程序 ```c++ #include #include #define Max_N 1005 #define Max_M 10005 using namespace std; int8_t gb_no[Max_N]; int32_t uset[Max_N]; int32_t urel[Max_N]; int8_t rmap[Max_N]; int32_t pair_rel[Max_M][2]; void init(int32_t n) { memset(gb_no, -1, sizeof(gb_no)); memset(urel, 0, sizeof(urel)); memset(rmap, 0, sizeof(rmap)); for (int32_t i = 1; i <= n; i++) { uset[i] = i; } return ; } int32_t father(int32_t ind, int32_t &rel) { if (uset[ind] == ind) { rel = 0; return ind; } int relt, fa; fa = father(uset[ind], relt); urel[ind] = relt ^ urel[ind]; uset[ind] = fa; rel = urel[ind]; return fa; } bool insert(int32_t a, int32_t b) { int32_t fa, fb, rela, relb, rel; fa = father(a, rela); fb = father(b, relb); rel = rela ^ relb ^ 1; if (fa == fb && rel != 0) return false; if (fa != fb) { uset[fa] = fb; urel[fa] = rel; } return true; } bool set_father_no(int32_t a) { int32_t fa, rela; fa = father(a, rela); if (gb_no[fa] >= 0 && gb_no[a] >= 0) { return (gb_no[fa] ^ gb_no[a]) == rela; } else if (gb_no[fa] == -1) { gb_no[fa] = gb_no[a] ^ rela; } return true; } int main() { int32_t n, m, x, y, ai, bi, t = 0; bool flag; while (scanf("%d%d%d%d", &n, &m, &x, &y) != EOF) { init(n); flag = true; assert(n > 1 && n <= 1000); assert(m >= 1 && m <= 10000); assert(x + y <= n); for (int32_t i = 0; i < m; i++) { scanf("%d%d", &ai, &bi); assert(ai >= 1 && ai <= n); assert(bi >= 1 && bi <= n); assert(ai != bi); rmap[ai] = rmap[bi] = 1; flag = flag && insert(ai, bi); } for (int32_t i = 0; i < x; i++) { scanf("%d", &ai); assert(ai >= 1 && ai <= n); if (gb_no[ai] != -1 && gb_no[ai] != 1) flag = false; gb_no[ai] = 1; flag = flag && set_father_no(ai); } for (int32_t i = 0; i < y; i++) { scanf("%d", &ai); assert(ai >= 1 && ai <= n); if (gb_no[ai] != -1 && gb_no[ai] != 0) flag = false; gb_no[ai] = 0; flag = flag && set_father_no(ai); } for (int32_t i = 1; i <= n; i++) { flag = flag && (rmap[i] != 0 || gb_no[i] != -1); } printf("%s\n", flag ? "YES" : "NO"); } return 0; } ``` #Problem B Regular Number ##提交状况:20/104 ##解题思路 经典的shift-and算法可以搞定问题,会了shift-and算法以后,就需要注意以下事项了: 1. 正则表达式的长度有1000,所以可以用一个Int64_t数字代表64位状态。 2. 做好映射表示,以免进行不必要的判断和计算,映射表示主要用来回答这个问题,正则表达式的第i个状态用状态数组的第几个数字的第几位表示。 具体的请看程序。 ##标准程序 ```c++ #include #include #include #define MAX_N 1005 #define MAX_LEN 10000005 #define MAX_ARR_LEN ((MAX_N >> 6) + 5) #define MASK 63 using namespace std; #define MYPRID PRId64 typedef uint64_t myint; myint num[10][MAX_ARR_LEN]; myint ret_n[MAX_ARR_LEN]; myint ind_x_arr[MAX_N]; myint ind_y_arr[MAX_N]; char str[MAX_LEN]; void init(myint n) { memset(num, 0, sizeof(num)); memset(ret_n, 0, sizeof(ret_n)); for (myint i = 0; i < n; i++) { ind_x_arr[i] = (i >> 6) + 1; ind_y_arr[i] = ((myint)1 << (i & MASK)); } } inline void set_one(myint *arr, myint n) { arr[ind_x_arr[n]] |= ind_y_arr[n]; } inline bool seek_one(myint *arr, myint n) { return arr[ind_x_arr[n]] & ind_y_arr[n]; } inline void left_move_one(myint *arr, myint n) { for (myint i = n; i >= 1; i--) { arr[i] <<= 1; arr[i] |= (!!(arr[i - 1] & 0x8000000000000000LL)); } set_one(arr, 0); } inline void and_opt(myint *arr1, myint *arr2, myint n) { for (myint i = 1; i<= n; i++) { arr1[i] &= arr2[i]; } } int main() { myint n, ai, bi, len, l; char ch; scanf("%"MYPRID, &n); init(n); for (myint i = 0; i < n; i++) { scanf("%"MYPRID, &ai); for (myint j = 0; j < ai; j++) { scanf("%"MYPRID, &bi); set_one(num[bi], i); } } scanf("%s", str); len = strlen(str); l = (n >> 6) + (!!(n & MASK)); for (myint i = 0; i < len; i++) { left_move_one(ret_n, l); and_opt(ret_n, num[str[i] - '0'], l); if (seek_one(ret_n, n - 1)) { ch = str[i + 1]; str[i + 1] = '\0'; printf("%s\n", str + i - n + 1); str[i + 1] = ch; } } return 0; } ``` #Problem C Game of Taking Stones ##提交情况:13/93 ##解题思路 题目是一个威佐夫博弈问题,可是数据范围太大原式在计算机种不是很容易解决问题,观察原威佐夫博弈的求解判别公式: ```math A_{k}=\lfloor k\times \frac{1+\sqrt{5}}{2}\rfloor ``` ```math B_{k}=A_{k}+k ``` 两堆石子数两满足上式,即是一个『先手必败态』。观察公式中$$A_{k}$$部分的表示,与菲波那切数列通项公式有些关系。而菲波那切数列第n项求解问题,使用『+/-』就可以搞定问题,所以标程的解决思路,是试图将上述公式转换成某种菲波那切数列问题的等价变换,这里只做提示,大家有兴趣可以自己进行详细推导,或找裁判讨论。 ##标准程序 ```c++ #include #include using namespace std; class BigInt { private : int flag, len, val[5000]; public : BigInt(); BigInt(const int &n); BigInt operator + (const int &n) const; BigInt operator - (const int &n) const; BigInt& operator = (const int &n); BigInt& operator = (const char* n); BigInt operator + (const BigInt &b) const; BigInt operator - (const BigInt &b) const; bool operator < (const BigInt &b) const; bool operator < (const int &n) const; bool operator == (const BigInt &b) const; bool operator == (const int &n) const; bool operator <= (const BigInt &b) const; bool operator <= (const int &n) const; bool operator > (const BigInt &b) const; bool operator > (const int &n) const; bool operator != (const BigInt &b) const; bool operator != (const int &n) const; void Print(); void Println(); int getLen(); }; int BigInt::getLen() { return this->len; } void BigInt::Print() { flag?printf(""):printf("-"); for (int i=this->len-1;i>=0;i--) printf("%d",this->val[i]); } void BigInt::Println() { this->Print(); printf("\n"); } BigInt::BigInt() { len=0; flag=true; val[len]=0; len++; } BigInt::BigInt(const int &n) { int temp(n); len=0; flag=(n>=0); temp=temp>=0?temp:-temp; while (temp!=0) { val[len]=temp%10; temp/=10; len++; } } BigInt BigInt::operator + (const BigInt &b) const { BigInt temp; BigInt temp1,temp2; temp1=*this; temp2=b; temp1.flag=temp2.flag=true; if (this->flag&&!b.flag) { temp=temp1-temp2; return temp; } if (!this->flag&&b.flag) { temp=temp2-temp1; return temp; } temp.len=b.len>this->len?b.len:this->len; for (int i=0;ilen) temp.val[i]+=this->val[i]; } for (int i=0;i=10) { if (i==temp.len-1) { temp.val[i+1]=1; temp.val[i]-=10; temp.len++; } else { temp.val[i+1]++; temp.val[i]-=10; } } temp.flag=this->flag; return temp; } BigInt BigInt::operator + (const int &n) const { BigInt temp(n); return (temp+*this); } BigInt BigInt::operator - (const BigInt &b) const { BigInt temp; BigInt temp1,temp2; temp1=*this; temp2=b; temp1.flag=temp2.flag=true; if (this->flag&&!b.flag) { temp=temp1+temp2; return temp; } if (!this->flag&&b.flag) { temp=temp1+temp2; temp.flag=false; return temp; } if (!this->flag&&!b.flag) { temp1.flag=false; temp=temp1+temp2; return temp; } if (*this==b) { temp=0; return temp; } if (*this=b.len) break; } while (temp.val[temp.len-1]==0&&temp.len>1) temp.len--; temp.flag=true; return temp; } BigInt BigInt::operator - (const int &n) const { BigInt temp; temp=n; return (*this-temp); } bool BigInt::operator < (const BigInt &b) const { if (this->flag&&!b.flag) return false; if (!this->flag&&b.flag) return true; if (this->lenlen>b.len) return false; for (int i=this->len-1;i>=0;i--) { if (this->val[i]!=b.val[i]) { if (this->val[i]flag; else return !this->flag; } } return false; } bool BigInt::operator < (const int &n) const { BigInt temp; temp=n; return (*this (const BigInt &b) const { return (b<*this); } bool BigInt::operator > (const int &n) const { BigInt temp; temp=n; return (temp<*this); } BigInt& BigInt::operator = (const int &n) { int temp; temp=n; len=0; flag=(n>=0); temp=temp>=0?temp:-temp; while (temp!=0) { val[len]=temp%10; temp/=10; len++; } if (len==0){val[0]=0;len=1;} return *this; } BigInt& BigInt::operator = (const char* n) { int j=0; int len=strlen(n); for (int i=len-1;i>=0;i--) { this->val[j]=(n[i]-'0')%10; j++; } this->len=j; return *this; } bool BigInt::operator != (const BigInt &b) const { if (*thism) { temp=m; m=n; n=temp; } we=0; ha=m; int j = -1; while (a[j+1] <= ha) { ++j; ha = ha - a[j]; we = we + b[j]; } while (j >= 3 && ha != 0) { if (a[j] <= ha) { ha = ha - a[j]; we = we + b[j]; } --j; } if (ha == 0 && n == (m - we)) printf("0\n"); else printf("1\n"); } return 0; } ``` #Problem D A Simple Math Problem ##提交情况:182/528 ##解题思路 题目中给出$$x,y$$两数的和以及两个数的最小公倍数: ```math X+Y=a ``` ```math LeastCommonMultiple(X,Y)=b ``` 设$$X,Y$$的最大公约数为$$c$$,则可得如下式子: ```katex \begin{array}{} (1):\space X=z_{1}\times c \\ (2):\space Y=z_{2}\times c \\ (3):\space X+Y=(Z_{1}+Z_{2})\times c \\ (4):\space LeastCommonMultiple(X,Y)=z_{1}\times z_{2}\times c \end{array} ``` - 因为$$\gcd(z_{1},z_{2})=1$$,所以$$\gcd((1),(2))=c$$,所以可得如下式子: ```katex \begin{array}{} z_{1}+z_{2}=\frac{(1)}{c} \\ z_{1}\times z_{2}=\frac{(2)}{c} \\ (z_{1}-z_{2})^{2}=(z_{1}+z_{2})^{2}-4\times z_{1}\times z_{2} \end{array} ``` - 从而可得$$z_{1}-z_{2}$$的值,得解。 ##标准程序 ```c++ #include #include #include #define NS_STR "No Solution" using namespace std; int32_t gcd(int32_t a, int32_t b) { if (!b) return a; return gcd(b, a % b); } int main() { int32_t a, b, c, d, e, f, g, x, y; while (scanf("%d%d", &a, &b) != EOF) { assert(a <= 2 * 10000 && a >= 1); assert(b <= 1000000000 && b >= 1); c = gcd(a, b); d = a / c; e = b / c; f = d * d - 4 * e; if (f < 0) { printf("%s\n", NS_STR); continue; } g = (int32_t)sqrt(f); if (g * g != f) { printf("%s\n", NS_STR); continue; } g = -g; x = (g + d) / 2 * c; y = a - x; assert(x > 0 && y > 0); printf("%d %d\n", x, y); } return 0; } ``` #Problem E Aninteresting game ##提交情况:29/134 ##解题思路 本题是一道计数问题。 1.第一个操作可以用前缀和的差来求解。添加完前$$x$$个数字,消耗$$\sum_{i=1}^{x}lowbit(i)$$点体力。通过枚举lowbit可以降低求和复杂度至$$logx$$ 2.第二个操作求$$x$$被加入新集合的次数。我们先考虑添加$$k$$时,$$[k-lowbit(k)+1, k-1]$$和$$k$$会被加入新集合。除去$$k$$,剩余的是$$k$$的最低非零位变成了0,更低的位**不全为0**的所有数字。反过来,先找到$$x$$的最低非零位,将某个比该位高的位置由0变成1得到$$k$$。添加$$k$$时,$$x$$会被加入新集合。这样的$$k$$的个数是:$$x$$二进制表示中比$$x$$最低非零位高的0的个数。再加上$$x$$本身就得到结果。 ##标准程序 ```c++ #include #include #include #include #include #include using namespace std; typedef int64_t ll; ll n, l, r, q, a; ll Cal(ll x) { ll ans = 0; for(int k = 0; (1ll<>(k+1)) + !!((1ll<4)$$最大的递增序列$$a_{1},a_{2}\ldots $$,有以下性质: 1)$$a{i+1}\leq 2$$ 2)最多有一个$$i$$,满足$$a_{i+1}-a_{i}=2$$ 3)$$1< a_{1}\leq 3$$ 反证法证明上述结论,简证如下: 证明性质1。假设存在$$i$$,满足$$a_{i+1}-a_{i}> 2$$,用$$a_{i+1}-1$$和$$a_{i}+1$$会得到更大的乘积,矛盾。 性质2。假设存在$$i< j$$,满足$$a_{i+1}-a_{i}=2$$,$$a_{j+1}-a_{j}> 2$$,用$$a_{j+1}-1$$和$$a_{i}+1$$代替$$a_{j+1}$$和$$a_{i}$$,会得到更大的乘积,矛盾。 性质3。如果$$a_{1}=1$$,那么它加到$$a_{i}(i>1)$$上去会得到更大的乘积。矛盾!如果$$a_{1}=4$$,分两种情况考虑。 1)$$a_{2}=5=2+3,2\times 3\times 4>4\times 5$$,得到一个$$a_{1}=2$$的更优解。矛盾!2)$$a_{2}=6,4+6=2+3+5,2\times 3\times 5>4\times 6$$,得到一个$$a_{1}=2$$的更优解。矛盾! 综上,解的结构是以下两种中的一种。 ```katex \begin{array}{} s=2\times 3\times \ldots \times (r-1)\times (r+1)\times \ldots \times n \\ s=3\times \ldots \times (r-1)\times (r+1)\times \ldots \times n \end{array} ``` 对于每一类最优解都是唯一确定$$r$$和$$n$$,所以找出一组猫足条件的$$r$$和$$n$$即可构造出最优解。 观察可知,与阶乘类似,所以可以用阶乘逼近答案。 首先,对于$$x$$,找出唯一确定的$$n$$和$$r^{\prime}$$,满足$$x=1+2+3+\ldots +n-r^{\prime}(0\leq r^{\prime}< n)$$。对$$r^{\prime}$$分类讨论。 ```katex \begin{array}{l} 1)r^{\prime}=0:x=2+3+\ldots +(n-1)+(n+1) \\ 2)r^{\prime}=1:x=2+3+\ldots +n \\ 3)r^{\prime}=2:x=3+4+\ldots +(n-1)+(n+1) \\ 4)r^{\prime}\geq 3:x=2+3+\ldots +(r^{\prime}-2)+r^{\prime}+\ldots +n \end{array} ``` - $$x\leq 10^9 \Rightarrow n< 10^5$$。预处理阶乘后,每次求出符合条件的$$n$$和$$r^{\prime}$$,对每种情况分类构造即可。 ##标准程序 ```c++ #include #include #include #include #include #include typedef int64_t ll; const ll MAX_T = 1000000; const ll MOD = 1e9 + 7; ll seri_times[MAX_T]; void init() { ll temp = 1; seri_times[0] = 1; for (ll i = 1; i < MAX_T; i++) { temp = (temp * i) % MOD; seri_times[i] = temp; } return ; } /* p - x * v = r x * v + r = 0 (mod p) x * r1 + v1 = 0 (mod p) v1 = -x * r1 (mod p) */ ll rev_num(ll k) { assert(k); if (k == 1) return 1; return ((-(MOD / k) * rev_num(MOD % k)) % MOD + MOD) % MOD; } int main() { ll tcase, n, x, r, ret; init(); scanf("%" PRId64, &tcase); while (tcase--) { scanf("%" PRId64, &n); if (__builtin_expect(!!(n == 1), 0)) { printf("1\n"); continue; } x = ((ll)sqrt(2 * n)); while (x * (x + 1) >> 1 < n) ++x; r = (x * (x + 1) >> 1) - n; assert(r >= 0); switch (r) { case 0 : ret = seri_times[x + 1] * rev_num(x); break; case 1 : ret = seri_times[x]; break; case 2 : ret = seri_times[x + 1] * rev_num(2 * x); break; default : ret = seri_times[x] * rev_num(r - 1); break; } ret %= MOD; printf("%" PRId64 "\n", ret); } return 0; } ``` #Problem G Garden of Eden ##提交情况:72/221 ##解题思路 树分治+枚举子集/DP 点的编号很小,所以可以用$$(1<< i)$$表示编号$$i$$的结点,问题转化为求权值**或和**为$$K=(1<< k)=1$$的有向路径条数。用树的点分治简化问题。问题转化为:给定一个集合,求该集合中**或和**为$$K$$的元素对,给出两种做法。 1)统计集合中元素值为$$x$$的个数$$num[x]$$,$$ans=\sum_{1\leq x\leq K}num[x]\times \sum_{y\space is\space subset \space of \space x}num[(x\oplus K)|y]$$ 2)进行dp。$$dp[i][st]$$表示低$$i$$位是$$st$$低$$i$$位的倍集(x是st的倍集:x&st=st),高位和st相同的元素个数。 (1<<(i-1))&st==0:$$dp[i][st]=dp[i-1][st]+dp[i-1][st\oplus ((1<<(i-1))]$$ (1<<(i-1))&st==1:$$dp[i][st]=dp[i-1][st]$$ ```katex ans=\sum_{0\leq x\leq K}num[x]\times dp[k][x\oplus K] ``` 第一种时间复杂度$$O(nlogn+n\times 3^{k})$$,第二种$$O(nlogn+n\times k\times 2^{k})$$ 对$$k=1$$特殊情况考虑一下(包含起点和终点相同的路径,用上述方法会出现重复计数)。 ##标准程序 ```c++ #include #include #include #include #include #include #include #define MP make_pair #define PII pair #define X first #define Y second #define ll long long #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; const int maxn = 50000+10; const int INF = 0x3f3f3f3f; const int maxk = 13; const int maxm = (1<<10)+10; vector g[maxn]; int n, k, s[maxn], vis[maxn], num[maxn], dp[maxk][maxn], w[maxn]; ll ans; void init(){ mem(vis, 0); ans = 0; } PII Find(int u, int f, int sum){ s[u] = 1; int lar = 0; PII tmp = MP(INF, 0); for(int i = 0; i < g[u].size(); i ++){ int v = g[u][i]; if(v == f || vis[v]) continue; PII x = Find(v, u, sum); s[u] += s[v]; lar = max(lar, s[v]); tmp = min(tmp, x); } lar = max(lar, sum-s[u]); return min(tmp, MP(lar, u)); } void dfs2(int u, int f, int x){ num[x] ++; s[u]=1; for(int i = 0; i < g[u].size(); i ++){ int v = g[u][i]; if(v == f || vis[v]) continue; dfs2(v, u, x|(1< 1) dfs(v, u, s[v]); } } int main() { while(scanf("%d%d", &n, &k) != EOF){ for(int i = 1; i <= n; i ++) scanf("%d", &w[i]), w[i] --, g[i].clear(); for(int i = 1; i < n; i ++){ int u, v; scanf("%d%d", &u, &v); g[u].push_back(v), g[v].push_back(u); } if(k == 1) { printf("%lld\n", 1ll*n*n); continue; } init(); dfs(1, 0, n); printf("%lld\n", ans); } return 0; } ``` #Problem H To begin or not to begin ##提交情况:216/298 ##解题思路 直接推公式即可。 先手获胜概率为$$\frac{\lfloor \frac{n+2}{2}\rfloor }{n+1}$$,向下取整。 n为偶数时,大于$$\frac{1}{2}$$;n为奇数时,等于$$\frac{1}{2}$$。所以n为偶数时,先手获胜;n为奇数时先手后手获胜概率相同。 标准程序 ```c++ #include #include #include using namespace std; int main(){ for(int n; cin>>n; ){ puts(n&1?"0":"1"); } return 0; } ``` #Problem I Convex ##提交情况:216/254 ##解题思路 用公式$$\frac{1}{2}\times sin\theta \times a \times b$$求三角形面积再求和 ##标准程序 ```c++ #include #include #include using namespace std; const double pi = acos(-1.0); int n, d; double sum; int main(){ while(scanf("%d %d", &n, &d) != EOF){ sum = 0; for(int i = 0, ang; i < n; ++i){ scanf("%d", &ang); sum += sin(1.0 * ang * pi / 180); } printf("%.3f\n", 0.5 * d * d * sum); } return 0; } ``` #Problem J Find Small A ##提交情况:215/360 ##解题思路 用位移操作,每次向右移动8位,统计小$$a$$的数量即可。 ##标准程序 ```c++ #include #define a1mask (97 << 0) #define mask1 (0x000000ff) using namespace std; int cnt_a(uint32_t ind) { uint32_t ret = 0; while(ind) { ret += !!((ind & mask1) == a1mask); ind >>= 8; } return ret; } int main() { int32_t n, ai, sum = 0; scanf("%d", &n); for (int32_t i = 0; i < n; i++) { scanf("%d", &ai); sum += cnt_a(ai); } printf("%d\n", sum); return 0; } ``` #Problem K Guess the number ##提交情况:20/73 ##解题思路 题目需要回答两个问题:1、最优策略需要猜几次;2、有多少种最优策略。 1、由题意,易得动规方程:$$f(x)=min(max(y,1+f(x-y))|y\in [1,x])$$,此方程复杂度太高,可以作为找规律方法的基础。现在我们采用另一种方式来思考这个问题: 现在来反推最优策略,设函数$$y=f(x)$$是区间长度位$$x$$时最优策略的猜数次数,并且容易得知以下事实: 当$$x_{1}\leq x_{2}$$时有$$f(x_{1})\leq f(x_{2})$$ 所以,$$y=f(x)\geq 1+f(x-y)$$,$$1+f(x-y)$$是$$f(x)$$的下限,现在讨论,$$f(x)$$到下限时的情况。 则$$f(x-f(x))=y_{1}=y-1$$,同时可得$$f(x+y+1)=y+1$$,则由公式可得如下$$f(x)$$到达下限时的$$x$$值 ```katex \begin{array}{} f(1)=1,f(3)=2,f(6)3,f(10)=4 \\ f(15)=5,f(21)=6,f(28)=7,f(36)=8 \end{array} ``` 则可知,$$f([2,3])=f(3)=2, f([4,6])=f(6)=3\ldots $$,由此我们得到了$$f(x)$$的值。 2、现在来讨论最优策略有多少种。由动规方程$$max(y,1+f(x-y))$$其中$$f(x-y)$$中$$y$$的上限为$$f(x)$$,$$f(x-y)$$的上限是$$f(x)-1$$,这两个上限大大缩小了动规方程中$$y$$的取值范围。具体的,请看标程。 ##标准程序 ```c++ #include #include #include #include #define Maxn 5000005 #define Mod_Num 100000073 using namespace std; typedef int64_t inta; const bool Output_flag = true; inta many_Time[Maxn + 5]; inta many_Acti[Maxn + 5]; void init() { memset(many_Time, 0, sizeof(many_Time)); memset(many_Acti, 0, sizeof(many_Acti)); } int64_t max(inta a,inta b) { if (a > b) return a; return b; } int main() { init(); inta *p = many_Time; inta *q = many_Acti; p[1] = 1; p[0] = 0; q[1] = 1; q[0] = 1; int32_t i, j, t, total_num, pre_total_num; i = 2; j = 2; pre_total_num = 1; while (j < Maxn) { t = i; total_num = pre_total_num + 1; total_num %= Mod_Num; pre_total_num = 0; while (j < Maxn && t--) { p[j] = i; q[j] = total_num; total_num = (total_num - q[j - i] + Mod_Num) % Mod_Num; pre_total_num += q[j]; pre_total_num %= Mod_Num; j++; } i++; } int32_t a,b; while (scanf("%d%d",&a,&b)!=EOF) printf("%" PRId64 " %" PRId64 "\n",p[b-a+1],q[b-a+1]); return 0; } ``` 标签: none
你最近这个解题频率看起来很亢奋啊……在做什么准备嘛
准备在区域赛打铁:hj-huamoji60:
代码挺多的额
节日快乐哦Baby(这个是读卑鄙吧~)
新年快乐
po主加油!
区域赛金牌!!
肝!