TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1716
  • 题目
  • P1716任意模数卷积 | 内含题解
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    输入两个长度为 \(n,m\) 的向量 \(a_0,\cdots,a_{n-1}\)\(b_0,\cdots,b_{m-1}\) ,计算它们的卷积 \(c_{0},\cdots,c_{n+m-2}\) ,计算结果对 \(M=10^9+8\) 取模。

    点击查看此题原内容“Week4 题解”

    一.GCD和LCM


    首先应注意到 n 必须为m 的因数,所以如果m%n!=0 即可输出无解。
    当 mn 时,显然只有1 个解。

    对于满足条件的数字a和b,易知需满足条件a*b
    n*m
    当 m=kn(k 为大于1 的整数时),令a=xn,b=yn。首先因为ab==mn,易得xy=k。
    其次,x,y 必须互质,否则a,b 的最大公因数就会大于n。
    注意到以上几点,原问题就化为:求使 k=xy 且x,y 互质的无序数对(x,y)的数量。
    将 k 分解质因数(复杂度O(sqrt(k)))。
    注:若两个数x和y互质,则有gcd(x,y)1

    参考如下代码:
    #include
    #include
    #include
    #include

    using namespace std;
    int i,n,m,k,v,ans=0;
    int gcd(int a,int b)//辗转相除法,求a和b的最大公约数
    {
    if(b!=0)return (gcd(b,a%b));
    else return (a);
    }

    int main()
    {
    scanf("%d%d",&n,&m);
    if(m%n!=0)printf("0\n");
    else
    {
    k=m/n;
    v=int(sqrt(k));
    for(i=1;i<=v;i++)
    if((k%i
    0)&&(gcd(i,k/i)==1))ans++; //i是k的因数且i与k/i互质
    printf("%d\n",ans);
    }
    return 0;
    }




    二.岛屿

    裸的并查集,只是用来复习一下并查集,不再啰唆了。




    三.生日蛋糕

    二分答案+搜索
    原问题:将n 阶方阵a[n][n]恰好分为n 个连通块,每个连通块的权和为wi,使min最大。
    转化为:将n 阶方阵恰好分为m 个连通块,满足所有wi>=limit,使得m 最大。二分limit即可。
    二分范围:min<=limit<=sum/m。


    通过上述分析,将这个子问题接着转化为:在 n 阶方阵中找出m 个连通块(不一定要覆盖满,可能会有剩的格),满足所有wi>=limit,使得m 最大。由于整块蛋糕是连通的,且所有权均为正数,所以这样转化是正确的,因为把剩下的几格随意归到其他连通块里,不影响m 的值。接着使劲搜即可。
    几个剪枝:
    ·若某个 a[i][j]>=limit,则把他单独归为一块。
    ·在 搜索的过程中,如果当前这块蛋糕的权和已经>=limit,则可停止扩展,而去扩展一块新的。
    ·如果没有希望超过目前的最优解,则跳出。
    ·如果一个连通分量的权值和<limit,则把它全部封住,因为它不可能成为一块蛋糕。


    输入格式

    第一行两个整数 \(n,m\)

    第二行 \(a_0,\cdots,a_{n-1}\)

    第三行 \(b_0,\cdots,b_{m-1}\)

    输入的 \(a_i,b_j\) 每个数都是在区间 \([0,M)\) 范围内的整数。

    输出格式

    输出一行 \(c_0,\cdots,c_{n+m-2}\)

    样例输入

    5 5
    1 2 3 4 5
    6 7 8 9 10

    样例输出

    6 19 40 70 110 114 106 85 50

    提示
    点击查看 大样例
    样例输入:
    
    30 30
    639090924 918301493 510077127 528513179 997382886 416810654 192129029 278272224 119359228 64758824 166695641 167615760 69889842 637640445 677168826 818249556 916051985 230433003 658982113 12177846 395515686 938970340 964931789 950903489 698997121 106707324 745692866 816618419 890894903 495631214
    943485509 4716370 738830560 727564312 940936353 248427069 919248921 355104762 175868774 824969078 672590851 234885435 427153125 874754790 424820931 350732835 181780661 244532185 785178880 455402402 410481200 1619318 66950248 309533640 276818679 29034849 70083619 592123979 33768802 103208977
    
    样例输出:
    
    903636156 844444153 17139893 753029037 460624000 141114027 142309577 555857941 562632258 62123099 618402632 571935308 271444925 8470370 933419027 573611211 567144569 807227958 641073498 626398761 195913770 976865998 916699534 465150245 446308016 915336915 847496573 88128422 168447941 464751281 293792835 630714515 313469340 834043842 538486691 197564641 252287539 532070575 916271176 388211401 734345343 611153670 802566956 870522777 945080680 50063093 525794900 409938865 104826651 794124479 212185514 252841661 832282577 367295569 712762988 224130367 494108651 14248075 156979358
    
    

    50%的数据, \(n,m\leq 2\times 10^3\)

    100%的数据, \(n,m\leq 2\times 10^5\)

    最后一个测试点开3秒,是用来让同学们带着目标去卡常数的