BZOJ 3823 定情信物

VictorWonder posted @ 2015年1月05日 15:22 in BZOJ with tags 解题报告 数论 递推 乘法逆元 , 901 阅读
这道题目刚出来的时候(大概是十二月二十七八日左右)觉得特别水,花了一点时间做了出来,谁知道最后还是被卡掉了……我的AC率啊!!!
 
于是稍稍推了一下递推式。
点动成线,所以一条线有两个点,线动成面,所以一个面有四条线,面的两边各有一条线,而两侧由于点的运动,又多了两条线。
面动成体,正对着的有两个面了,四周由于四条边在动,形成了四个新的面……
这样下去,一个k(k>0)维超正方体是由k*2个k-1维超正方体组成的。
还有一个规律,对于一个k维超正方体来说,k维的超正方体有1个,k-1维的超正方体有k*2个。
但是k-2维的超正方体并非k*2*(k-1)*2个,因为每两个k-1维超正方体之间都有2个k-2维的超正方体相交,所以要除以2,相对应的,k-3维超正方体=k-2维超正方体的数目*(k-2)*2/3……
但是,这道题最主要的问题是取模,有除法,所以需要求逆元,但是,用exgcd求逆元是O(log n)的,不过,Claris向我提供了一份O(n)求出所有逆元的代码,到目前为止,我还没有搞清楚这段代码的原理TAT
我怕这道题目变成权限题,于是马上就提交了这题,结果,有人加强了一下数据,把大多数人都卡掉了,于是我整个人就顿时不好了。
原来,还有一种神奇的情况就是,维数是模数的倍数,那么就不能求逆元了,我立马就束手无策了,好在Claris提供了帮助,对于一个数x,如果[tex]x=p*mod^k[/tex],那么我们就不用管mod,将其逆元当作是p的逆元,递推的时候,再计算一下,当前的答案是否为mod的倍数,如果是mod的倍数的话,那么答案就是0,否则答案就是我们求出来的值。另外,如果模的数是2的话,发现答案永远是1,可以特判加速。
具体的可以看一下代码。
PS:这种时候,递推式算好像比通项公式要快。
 
UPD:关于线性递推求逆元的证明
    对于一个数i,其逆元inv[i]满足i*inv[i]%P=1
    设P=i*j+k,则j=P/i,k=P%i
    所以i=(P-k)/j%P=-k/j
    那么,inv[i]=1/i=-j/k=-j*inv[k]
    证毕
 
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=10001000;
int n,x,num;
ll t,last,ans=1,mod;
int r[N],a[N];
char c[N];
int main() {
    int i;
    scanf("%d%lld",&n,&mod);
    if (mod==2) return puts("1"),0;
    for(r[1]=a[1]=1,i=2;i<=n;i++) if (i%mod==0) {
        x=i;
        while (x%mod==0) {
            c[i]++;
            x/=mod;
        } r[i]=r[a[i]=x];
    } else {
        a[i]=i;
        if (i>=mod) r[i]=r[i%mod];
        else {
            r[i]=-(ll)r[mod%i]*(mod/i)%mod;
            while (r[i]<0) r[i]+=mod;
        }
    }
    for (last=i=1;i<=n;i++) {
        last=(((last*a[n-i+1]%mod)<<1)%mod)*r[i]%mod;
        num+=c[n-i+1]-c[i];
        if (!num) ans^=last;
    } cout<<ans<<endl;
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter